Manacher's algorithm
hardThe `#` padding removes the even/odd split, and palindromes mirroring inside palindromes remove the quadratic expansion. Two ideas, one linear algorithm.
O(n)Space O(n)Saved in this browser - no sign-up, nothing sent anywhere.
How manacher's algorithm works
Expanding around every centre finds the longest palindromic substring in O(n²), and the even/odd split makes it fiddly: aba has a centre character, abba does not. Manacher removes the split first - interleave # separators so abba becomes #a#b#b#a#. Every palindrome in the padded string is odd-length with a genuine centre, and the radius there equals the palindrome's length in the original string.
The linear-time half is a mirror argument. Track the palindrome reaching furthest right, with its centre and right boundary. A new index i inside that palindrome has a mirror at 2·centre - i, and whatever palindrome sits at the mirror is guaranteed at i too - the two sides are identical by definition. So the radius starts at min(right - i, p[mirror]) rather than at 0.
The clamp is the subtle part: the mirror's palindrome may run past the enclosing boundary, where nothing has been compared, so nothing beyond right - i can be trusted. After the free start, expand normally; when a palindrome pushes past right, the boundary advances. Since right only ever moves forward, total expansion across the run is O(n) - the same argument that makes the Z-algorithm linear.
Step by step
- Pad abba to #a#b#b#a# - nine characters, every palindrome now odd-length. All radii start at 0, centre and right at 0.
- i = 1 (a): the neighbouring separators match, then expansion hits the left edge. Radius 1; centre moves to 1, right to 2.
- i = 3 (b): its separator pair matches, then a against b fails. Radius 1; centre 3, right 4. Separators between unequal letters stay at 0.
- i = 4 (the middle #): four expansions succeed - b b, # #, a a, # # - so radius 4, which is abba itself. Centre 4, right 8.
- i = 5 (b): its mirror is 3 with radius 1, and min(right - i, 1) = min(3, 1) = 1 - copied free; the one extension attempt fails.
- The remaining positions inherit 0 or 1 the same way and never beat 4. Best centre 4: start = (4 - 4) / 2 = 0, answer abba.
Complexity
| Worst case time | O(n) |
|---|---|
| Space | O(n) |
The right boundary only moves forward, capping total expansion at n.
Reference implementation
Python
def manacher(s):
"""Longest palindromic substring in O(n)."""
t = "#" + "#".join(s) + "#"
n = len(t)
p = [0] * n
centre = right = 0
for i in range(n):
if i < right:
p[i] = min(right - i, p[2 * centre - i]) # reuse the mirror
while (i - p[i] - 1 >= 0 and i + p[i] + 1 < n
and t[i - p[i] - 1] == t[i + p[i] + 1]):
p[i] += 1
if i + p[i] > right:
centre, right = i, i + p[i]
best = max(range(n), key=lambda i: p[i])
start = (best - p[best]) // 2
return s[start:start + p[best]]JavaScript
function manacher(s) {
const t = "#" + [...s].join("#") + "#";
const n = t.length, p = new Array(n).fill(0);
let centre = 0, right = 0;
for (let i = 0; i < n; i++) {
if (i < right) p[i] = Math.min(right - i, p[2 * centre - i]);
while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n &&
t[i - p[i] - 1] === t[i + p[i] + 1]) p[i]++;
if (i + p[i] > right) { centre = i; right = i + p[i]; }
}
let best = 0;
for (let i = 1; i < n; i++) if (p[i] > p[best]) best = i;
const start = (best - p[best]) / 2;
return s.slice(start, start + p[best]);
}Worth noticing
The `#` padding removes the even/odd case split
'abba' has no single centre character; 'a#b#b#a' does. Interleaving separators makes every palindrome odd-length, so one loop handles both cases and p[i] conveniently equals the palindrome's length in the original string.
Palindromes mirror inside a palindrome
If i lies inside a known palindrome centred at c, the radius at i's mirror is a valid starting guess - the two sides are identical by definition. That is the reuse that makes this linear.
`min(right - i, ...)` is the safety clamp
The mirror's palindrome may run past the boundary of the enclosing one, where nothing is known. Clamping to right − i stops the algorithm from trusting information it does not have.
O(n) versus the O(n²) expand-around-centre
The obvious approach tries all 2n−1 centres and expands each, which is quadratic. Manacher expands too, but `right` only moves forward, capping total expansion work at n.
Common pitfalls
- Dropping the min(right - i, p[mirror]) clamp. The mirror's palindrome can poke past the boundary of the enclosing one, where nothing is known - trusting it writes radii that are simply wrong.
- Expanding without bounds checks. The loop must confirm i - p[i] - 1 >= 0 and i + p[i] + 1 < n before comparing, or edge palindromes walk off the padded array.
- Fumbling the unpadding arithmetic. Here p[best] already equals the palindrome's length in the original string and its start is (best - p[best]) / 2 - re-deriving that under pressure is a classic stumble.
- Updating centre and right on every index instead of only when i + p[i] > right. Let right retreat and the linear-time argument collapses on repetitive strings like aaaa.
Where it is used
- The canonical O(n) answer to longest palindromic substring - one of the most-asked hard string interview questions.
- Counting palindromic substrings: each padded centre with radius r contributes r / 2 rounded up, so the count reads off the array.
- Palindrome partitioning and shortest-palindrome variants, where a full radius table replaces expanding from scratch at every position.
- Any task needing every maximal palindrome at once - the radius array delivers all of them in a single pass.
Frequently asked questions
What is the time and space complexity of Manacher's algorithm?
O(n) time and O(n) space for the padded string and its radius array. The right boundary only ever moves forward, so expansion successes across the whole run total at most n. The player's closing step shows the actual comparison count next to the roughly n²/2 that expanding around every centre would need.
Why does Manacher's algorithm insert # characters?
Even-length palindromes have no centre character - abba's centre falls between the two b's. Interleaving separators gives every palindrome, even or odd, a real centre in the padded string, so one loop handles both. A bonus of the encoding: the radius at each padded centre equals the palindrome's length in the original.
How is Manacher's algorithm different from expand around centre?
Expand-around-centre tries all 2n - 1 centres independently, re-expanding each from scratch - O(n²) on strings like aaaa. Manacher expands too, but seeds each position with a mirrored radius from inside the current rightmost palindrome, so comparisons only ever happen in new territory. The seeding is the entire difference.
Can Manacher's algorithm find all palindromes, not just the longest?
Yes. It computes the maximal radius at every padded centre, and every palindromic substring is nested inside one of those maxima. The longest is a max over the array; counting and enumeration problems use the same array with no extra scanning.