What is Manacher's Algorithm?
Learn how Manacher's algorithm finds the longest palindromic substring in O(n) time using mirrored radii.
Expected Interview Answer
Manacher's algorithm finds the longest palindromic substring in a string in O(n) time by reusing previously computed palindrome-radius information from a mirrored position inside the current rightmost-known palindrome, avoiding the O(n^2) worst case of expanding around every center independently.
The algorithm first transforms the string by inserting a separator character (like '#') between every character and at both ends, which unifies odd- and even-length palindromes into a single odd-length case to handle. It then scans left to right, maintaining the center and right boundary of the rightmost palindrome found so far; for each new position, if it falls inside that boundary, its palindrome radius can be initialized using its mirror position's already-known radius (clamped to the boundary), instead of starting expansion from zero. Only when the mirrored value isn't conclusive does the algorithm actually expand character by character, and each such expansion extends the rightmost boundary, which is what bounds the total expansion work across the whole scan to O(n). This mirroring trick is the same amortized-cost idea used in other linear-time string algorithms, and it's what separates Manacher's from the naive expand-around-center approach, which is O(n^2) in the worst case (e.g., a string of all the same character).
- Guaranteed O(n) time, unlike the O(n^2) expand-around-center approach
- Handles odd and even length palindromes uniformly via the separator trick
- Amortized cost bounded by the rightmost boundary never shrinking
- Finds every maximal palindrome centered at each position, not just the longest
AI Mentor Explanation
Manacher's algorithm is like a groundskeeper checking how symmetric each row of a stadium's seating is around its center aisle, reusing work from a mirrored row instead of measuring every row from scratch. Once the groundskeeper has measured the widest known symmetric block so far, checking a new row that falls inside that block can start from the already-known symmetry of its mirror row on the other side, instead of comparing seat by seat from zero. Only when the mirrored measurement isn't conclusive does the groundskeeper actually walk outward seat by seat, and each such walk extends how far the known symmetric block reaches. This is why the whole stadium can be checked for symmetry in time proportional to its size, not the square of it.
Step-by-Step Explanation
Step 1
Transform the string
Insert a separator like '#' between every character and at both ends so odd and even palindromes are handled uniformly.
Step 2
Track center and right boundary
Maintain the center and right edge of the rightmost palindrome discovered so far during the scan.
Step 3
Mirror to initialize each radius
For each new position inside the current boundary, initialize its palindrome radius from its mirror position's radius, clamped to the boundary.
Step 4
Expand only when needed and update boundary
Expand character by character only past what the mirror guarantees, then update the center and right boundary if extended further.
What Interviewer Expects
- Explain why the separator transform unifies odd and even length palindromes
- Describe the mirror trick and why it avoids redundant expansion
- Justify the O(n) amortized time via the boundary never shrinking
- Contrast with the naive O(n^2) expand-around-center approach and when the simpler approach is acceptable
Common Mistakes
- Forgetting to clamp the mirrored radius to the current right boundary before expanding
- Not transforming the string, leading to separate messy handling of odd/even cases
- Claiming O(n) without explaining the amortized argument for why expansions are bounded
- Confusing the center/boundary update rule, causing incorrect radius values
Best Answer (HR Friendly)
“Manacher's algorithm finds the longest palindrome in a string in linear time by reusing what it already learned about a mirrored position instead of re-checking every possible center from scratch. I'd bring it up when a problem specifically calls for the longest palindromic substring efficiently, since the naive approach is quadratic.”
Code Example
def longest_palindrome(s):
if not s:
return ""
t = "#" + "#".join(s) + "#"
n = len(t)
radius = [0] * n
center = right = 0
for i in range(n):
if i < right:
mirror = 2 * center - i
radius[i] = min(right - i, radius[mirror])
while (i - radius[i] - 1 >= 0 and i + radius[i] + 1 < n
and t[i - radius[i] - 1] == t[i + radius[i] + 1]):
radius[i] += 1
if i + radius[i] > right:
center, right = i, i + radius[i]
max_len, center_index = max((r, i) for i, r in enumerate(radius))
start = (center_index - max_len) // 2
return s[start:start + max_len]Follow-up Questions
- Why does Manacher's algorithm insert a separator character between every letter?
- How would you count all palindromic substrings using the radius array?
- Why is the naive expand-around-center approach O(n^2) in the worst case?
- How does Manacher's algorithm compare to using suffix arrays for palindrome problems?
MCQ Practice
1. What is the time complexity of Manacher's algorithm?
The mirror trick bounds total expansion work by the right boundary, which only ever grows, giving O(n).
2. Why does Manacher's algorithm insert separator characters into the string?
The separator ensures every palindrome in the transformed string has odd length, simplifying the algorithm.
3. What does Manacher's algorithm reuse to avoid redundant expansion?
Mirroring within the known rightmost palindrome lets the algorithm skip re-verifying already-known symmetric characters.
Flash Cards
What problem does Manacher's algorithm solve, and in what time? — Finding the longest palindromic substring in O(n) time.
Why does Manacher's algorithm insert '#' separators? — To turn every palindrome, odd or even length, into an odd-length palindrome in the transformed string.
What does Manacher's algorithm mirror to save work? — The palindrome radius from the mirrored position relative to the current center, clamped to the right boundary.
What is the naive alternative's complexity? — O(n^2), from expanding around every center independently without reuse.