How Do You Find the Longest Palindromic Substring?
Learn the expand-around-center approach for finding the longest palindromic substring in O(n squared) time.
Expected Interview Answer
The expand-around-center approach finds the longest palindromic substring in O(n²) time and O(1) extra space by treating every index (and every gap between indices, for even-length palindromes) as a potential center and growing outward while characters match, which beats brute-force O(n³) checking of every substring and is simpler than Manacher's O(n) algorithm while still being efficient enough for most interviews.
There are 2n - 1 possible centers — n single-character centers for odd-length palindromes and n-1 gaps for even-length palindromes — and expanding from each center takes O(n) worst case, giving O(n²) overall with O(1) space since no extra data structure is built beyond tracking the best start and length seen so far. This dominates the naive approach of generating all O(n²) substrings and checking each in O(n) for palindrome-ness, which is O(n³). For truly linear time, Manacher's algorithm exploits palindrome symmetry to avoid re-expanding already-known regions, but it is rarely required in an interview unless explicitly asked for O(n). Dynamic programming is another valid O(n²) time and O(n²) space approach, building a table where dp[i][j] is true if the substring from i to j is a palindrome, but expand-around-center is preferred for its O(1) space.
- O(n²) time with O(1) extra space
- Handles both odd- and even-length palindromes uniformly
- Simpler to implement correctly than Manacher's algorithm
- Beats brute-force O(n³) substring checking
AI Mentor Explanation
Finding the longest palindromic substring is like standing at every ball in an over's shot sequence and checking how far the shots mirror symmetrically outward before diverging, treating each ball — and each gap between two balls — as a potential mirror point. From ball five, you check if ball four matches ball six, then ball three matches ball seven, expanding outward until the shots no longer mirror, then move to the next ball and repeat. Checking all 2n-1 possible mirror points this way costs far less than generating every possible shot-sequence window and checking each one for symmetry from scratch. The scorer just remembers the longest mirrored stretch found so far, without storing any extra data beyond that record.
Step-by-Step Explanation
Step 1
Enumerate all possible centers
Consider each index (odd-length center) and each gap between indices (even-length center), 2n-1 total.
Step 2
Expand outward from each center
While the left and right characters match and are in bounds, move both outward by one.
Step 3
Track the best window seen
Compare the current expansion's length against the best found so far and update start/length.
Step 4
Return the substring from the best window
Slice the original string using the tracked best start index and length, O(n²) total time, O(1) extra space.
What Interviewer Expects
- Cover both odd- and even-length palindrome centers
- State O(n²) time, O(1) space for expand-around-center
- Compare against brute force O(n³) and mention DP O(n²) time/space as an alternative
- Mention Manacher's algorithm as the O(n) solution if pushed for optimal
Common Mistakes
- Forgetting even-length palindromes by only checking single-character centers
- Off-by-one errors in the expansion boundary conditions
- Claiming O(n) complexity without implementing Manacher's algorithm
- Using brute-force substring generation and calling it optimal
Best Answer (HR Friendly)
“I would treat every character, and every gap between characters, as a possible center of a palindrome, then grow outward from each one as long as both sides keep matching. Whichever center grows the widest before breaking gives me the longest palindrome, and I just track the best one I have seen as I go.”
Code Example
def longest_palindrome(s):
if not s:
return ""
def expand(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return left + 1, right - 1
start, end = 0, 0
for i in range(len(s)):
l1, r1 = expand(i, i) # odd length
l2, r2 = expand(i, i + 1) # even length
if r1 - l1 > end - start:
start, end = l1, r1
if r2 - l2 > end - start:
start, end = l2, r2
return s[start:end + 1]Follow-up Questions
- How does Manacher's algorithm achieve O(n) time for this problem?
- How would you count the total number of palindromic substrings instead?
- How would the dynamic programming table approach differ in space usage?
- How would you find the longest palindromic subsequence instead of substring?
MCQ Practice
1. What is the time complexity of the expand-around-center approach?
Each of the 2n-1 centers can expand up to O(n) times, giving O(n²) overall.
2. Why must both index-centers and gap-centers be checked?
Odd-length palindromes center on a single character; even-length palindromes center on a gap between two characters.
3. What algorithm achieves O(n) time for this exact problem?
Manacher's algorithm reuses previously computed palindrome radii to avoid redundant expansion, achieving linear time.
Flash Cards
What is the time and space complexity of expand-around-center? — O(n²) time, O(1) extra space.
How many total centers must be checked for a string of length n? — 2n - 1: n single-character centers plus n-1 gap centers.
What algorithm solves this problem in O(n)? — Manacher's algorithm, using palindrome symmetry to avoid redundant expansions.
What is the brute-force complexity for this problem? — O(n³): generating O(n²) substrings and checking each for palindrome-ness in O(n).