0
0
Palindrome problems are a classic in computer science, especially in interviews. Today, let’s explore a common variant: finding the longest palindromic substring in a given string using Go (Golang). We’ll walk through the logic behind a clean and efficient solution.
Problem Statement
Input: "babad"
Output: "bab" // or "aba"
Input: "cbbd"
Output: "bb"
Understanding the Approach
To solve this problem, we use the “expand around center” technique. A palindrome mirrors around its center, and a string of length n has 2n - 1 such centers (each character, and each gap between characters).
This method checks all possible centers and expands outwards while characters on both sides are equal.
We handle two types of centers:
- Odd-length palindrome: e.g., “racecar” has center ‘e’
- Even-length palindrome: e.g., “abba” has center between the two b’s
func longestPalindrome(s string) string {
if len(s) == 1 {
return s
}
res := ""
resMax := 0
for j := 0; j < len(s); j++ {
// Odd length palindrome
l, r := j, j
for l >= 0 && r < len(s) && s[l] == s[r] {
if resMax < r - l + 1 {
res = s[l : r+1]
resMax = r - l + 1
}
l--
r++
}
// Even length palindrome
l, r = j, j+1
for l >= 0 && r < len(s) && s[l] == s[r] {
if resMax < r - l + 1 {
res = s[l : r+1]
resMax = r - l + 1
}
l--
r++
}
}
return res
}
Step-by-Step Explanation
- Edge Case: If the input string has only one character, we return it immediately.
- Iterate through the string: Treat each character (and each gap) as a potential center.
- Expand Around Center:
- For odd-length palindromes, start with the same left and right (
j, j) - For even-length palindromes, start with adjacent characters (
j, j+1)
- For odd-length palindromes, start with the same left and right (
- Check and Update:
- As long as the characters on both ends match, keep expanding.
- If the length of the current palindrome is greater than the previously stored one, update the result.
Time and Space Complexity
Space Complexity: O(1) — We only use a few variables.
Time Complexity: O(n²) — Each center can expand up to the length of the string.
TEST
fmt.Println(longestPalindrome("babad")) // Output: "bab" or "aba"
fmt.Println(longestPalindrome("cbbd")) // Output: "bb"
fmt.Println(longestPalindrome("a")) // Output: "a"
fmt.Println(longestPalindrome("ac")) // Output: "a" or "c"
This solution is elegant and efficient for strings of moderate length. If performance is critical for very large strings, advanced methods like Manacher’s Algorithm can achieve O(n) time complexity, though at the cost of more complexity.
About Author
