Introduction
A palindrome is a string that reads the same forwards and backwards, such as 'racecar' or 'level'. The longest palindromic substring problem asks for the longest contiguous substring of a given string that is a palindrome. A brute-force check of every substring costs O(n^3), but the expand-around-center technique reduces this to O(n^2) by exploiting the fact that every palindrome is centered at either a single character (odd length) or between two characters (even length).
Cricket analogy: A scorecard sequence like 'W-1-4-1-W' reading the same forwards and backwards is a palindrome, and finding the longest such symmetric run of overs by checking every possible span costs O(n^3), while expand-around-center exploits that every symmetric run has a single central over or a gap between two overs.
Algorithm/Syntax
def longest_palindrome(s: str) -> str:
if not s:
return ""
def expand(left: int, right: int) -> tuple[int, int]:
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
# left/right have overshot by one on each side
return left + 1, right - 1
start, end = 0, 0
for center in range(len(s)):
l1, r1 = expand(center, center) # odd-length palindromes
if r1 - l1 > end - start:
start, end = l1, r1
l2, r2 = expand(center, center + 1) # even-length palindromes
if r2 - l2 > end - start:
start, end = l2, r2
return s[start:end + 1]Explanation
For each index in the string, the algorithm treats it as a potential center and expands outward in both directions as long as the characters on each side match. There are two kinds of centers: a single character (for odd-length palindromes like 'aba') and a gap between two adjacent characters (for even-length palindromes like 'abba'). By trying both center types at every position and tracking the widest expansion found, the algorithm covers all possible palindromic substrings in O(n) centers x O(n) expansion = O(n^2) time, without needing O(n^3) brute-force substring generation. For truly linear time, Manacher's algorithm can find the longest palindromic substring in O(n) by reusing previously computed palindrome radii, but it is more intricate to implement correctly.
Cricket analogy: Treating each over as a potential center and expanding outward to check matching scoring patterns on both sides covers odd-length runs like a single big over and even-length runs like two tied overs, in O(n) centers times O(n) expansion, versus Manacher's trickier O(n) reuse of prior symmetry data.
Example
s = "babadada"
print(longest_palindrome(s)) # e.g. "adada" (length 5)
# Trace highlights:
# center=1 ('a' in 'bab'): expand -> "bab" (length 3)
# center=4..5 gap in 'adada': expand -> "adada" (length 5), which becomes the new best
# Final answer: the widest palindrome found across all centers, "adada"Complexity
The expand-around-center approach runs in O(n^2) time in the worst case (e.g., a string of all identical characters, where every expansion runs nearly the full length of the string) and O(1) extra space besides the output. Dynamic programming with a 2D boolean table also solves this problem in O(n^2) time but uses O(n^2) space, making expand-around-center generally preferable. Manacher's algorithm achieves O(n) time and O(n) space by cleverly reusing symmetry information from previously computed palindromes, but the expand-around-center method is usually sufficient and much simpler to reason about and implement correctly in an interview or practical setting.
Cricket analogy: Expand-around-center runs O(n^2) worst case on a string of near-identical dot balls where every expansion nearly spans the whole innings, uses O(1) extra space, and while a 2D DP table also solves it in O(n^2) time it needs O(n^2) space, so expand-around-center is generally preferred for practical scorecard analysis.
Key Takeaways
- Every palindrome is centered either at a single character (odd length) or between two characters (even length); checking both cases covers all palindromes.
- Expand-around-center runs in O(n^2) time and O(1) extra space, much better than the O(n^3) brute-force enumeration of all substrings.
- A 2D DP table also achieves O(n^2) time but costs O(n^2) space, so expand-around-center is usually preferred.
- Manacher's algorithm solves the problem in O(n) time by reusing previously computed palindrome information, but is more complex to implement.
Practice what you learned
1. How many possible palindrome centers does a string of length n have?
2. What is the time complexity of the expand-around-center approach to find the longest palindromic substring?
3. Why does the algorithm check expand(center, center) and expand(center, center+1) separately?
4. What is the time complexity of Manacher's algorithm for this problem?
5. What is the extra space complexity of the expand-around-center approach (excluding the output)?
Was this page helpful?
You May Also Like
Naive String Matching and KMP
Compare brute-force substring search with the Knuth-Morris-Pratt algorithm, which uses a failure function to avoid re-scanning characters.
Introduction to Dynamic Programming
Learn what dynamic programming is and the two conditions — overlapping subproblems and optimal substructure — that make it applicable.
Recursion Basics
Learn how functions that call themselves can solve problems by breaking them into smaller subproblems.