Introduction
Palindromes are strings that read the same forwards and backwards. In LeetCode 5, you're asked to find the longest palindromic substring in a given string. This problem is a great way to learn about string traversal and center-expansion techniques. In this article, we'll explore the most intuitive and efficient solution using Go (Golang).
Problem Statement
Given a string s, return the longest palindromic substring in s.
Example
go
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
go
Input: s = "cbbd"
Output: "bb"
Brute Force Approach (Inefficient)
Check every possible substring and see if it's a palindrome — O(n³) time.
Optimized Approach: Expand Around Center
Every palindrome is centered at one or two characters. So, we can expand from each possible center and track the longest one.
Key Idea:
- A palindrome can have:
- Odd length: single center (e.g.,
"racecar")
- Even length: double center (e.g.,
"abba")
We expand around every index (and pair of indices), checking for the longest palindrome.
Go Implementation
go
package main
import (
"fmt"
)
func longestPalindrome(s string) string {
if len(s) < 2 {
return s
}
start, end := 0, 0
for i := 0; i < len(s); i++ {
len1 := expandAroundCenter(s, i, i) // Odd length
len2 := expandAroundCenter(s, i, i+1) // Even length
maxLen := max(len1, len2)
if maxLen > end-start {
start = i - (maxLen-1)/2
end = i + maxLen/2
}
}
return s[start : end+1]
}
func expandAroundCenter(s string, left, right int) int {
for left >= 0 && right < len(s) && s[left] == s[right] {
left--
right++
}
return right - left - 1
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
input := "babad"
result := longestPalindrome(input)
fmt.Printf("Longest palindromic substring: %s\n", result)
input2 := "cbbd"
result2 := longestPalindrome(input2)
fmt.Printf("Longest palindromic substring: %s\n", result2)
}
How It Works
Let’s take "babad" as an example:
- At index
0 → expand "b" → length = 1
- At index
1 → expand "aba" → length = 3
- At index
2 → expand "bab" → length = 3
- And so on...
We track the longest palindrome found during each expansion.
Time and Space Complexity
- Time Complexity: O(n²) — each center expands in worst-case linear time.
- Space Complexity: O(1) — constant extra space.
Alternative: Dynamic Programming (More Code, Same Time)
There’s also a DP solution that stores whether s[i:j] is a palindrome in a 2D table. However, it’s not faster and uses O(n²) space, so "expand around center" is generally preferred in interviews.
Key Takeaways
- Expand-around-center is simple, fast, and interview-friendly.
- Always check for both odd and even-length palindromes.
- The approach avoids extra space and handles edge cases elegantly.