Solving the LeetCode "Longest Palindromic Substring" Problem in Go

Difficulty: Medium | Tags: Two Pointers, String, Dynamic Programming

Introduction

Finding the longest palindromic substring is a classic problem in computer science, often used to test understanding of string manipulation and dynamic programming. A palindrome reads the same backward as forward, and identifying the longest such substring efficiently is key.

Problem Analysis

Given a string, we need to find the longest contiguous substring that is a palindrome. For example, in "babad", the longest palindromic substrings are "bab" or "aba". In "cbbd", the answer is "bb". The challenge lies in optimizing the solution to handle longer strings efficiently.

Solution Approach

We can solve this problem using a dynamic programming approach or by expanding around the center. The latter is more efficient for this problem. The idea is to treat each character (and each pair of characters) as the center of a potential palindrome and expand outward to find the longest possible palindrome.

Go Implementation

package main
func longestPalindrome(s string) string {
    if len(s) < 2 {
        return s
    }
    start, maxLength := 0, 1
    for i := 0; i < len(s); i++ {
        expandAroundCenter(s, i, i, &start, &maxLength)   // Odd length
        expandAroundCenter(s, i, i+1, &start, &maxLength) // Even length
    }
    return s[start : start+maxLength]
}
func expandAroundCenter(s string, left, right int, start, maxLength *int) {
    for left >= 0 && right < len(s) && s[left] == s[right] {
        left--
        right++
    }
    currentLength := right - left - 1
    if currentLength > *maxLength {
        *maxLength = currentLength
        *start = left + 1
    }
}

Complexity Analysis

The time complexity of this solution is O(n^2), where n is the length of the string. This is because we expand around each center (2n-1 centers in total) and each expansion can take O(n) time in the worst case. The space complexity is O(1) as we only use a constant amount of extra space.

Testing and Examples

Test cases:

• Input: "babad" → Output: "bab" or "aba"
• Input: "cbbd" → Output: "bb"
• Input: "a" → Output: "a"
• Input: "ac" → Output: "a" or "c"

Best Practices and Tips

Key takeaways:

• Use the expand-around-center approach for better efficiency.
• Handle edge cases like single-character strings or empty strings.
• Optimize by avoiding unnecessary computations during expansion.