Manacher's Algorithm
Manacher's algorithm finds the radius of the longest palindrome centered at every position in O(n) total — by reusing palindrome radii already computed within a known enclosing palindrome. It is the O(n) upgrade to the O(n²) expand-around-center approach.
Table of contents
Why O(n) is possible
Expand-around-center does redundant work: if a large palindrome "ABACABA" is centered at position 3, positions 2 and 4 are mirrors of each other, and any palindrome centered at 4 is already implied by the palindrome at 2. Manacher's reuses this information.
The key insight: if position i falls inside a known palindrome [L, R] centered at C, the palindrome radius at i is at least min(radius[mirror], R - i) where mirror = 2*C - i. Start expansion from there instead of from 0.
The hotel room mirror story
A real-life story
A hotel corridor has perfectly symmetric rooms on both sides of a centre. A room inspector visiting room 10 thinks: "Room 10 is a mirror of room 6 (since the centre is at room 8). Room 6 had a confirmed clean rating of 3 rooms deep. So room 10 is also clean at least 3 rooms deep — unless I reach the edge of the wing I know about. I'll start my inspection from position 3, not from the beginning."
This is exactly Manacher's algorithm. The "wing" is the [L, R] window. The "mirror rating" is p[mirror]. We start each new position's expansion from cached knowledge and only do new work when we go beyond the known window.
The preprocessing trick: handle even palindromes
Insert a separator # between every character (and at both ends) to unify odd and even palindromes into odd-only:
"abc" → "#a#b#c#" (length 2n+1, always odd)
"abba" → "#a#b#b#a#"
Now every palindrome in the transformed string is odd-length. The radius of a #-centered palindrome corresponds to an even-length palindrome in the original; a character-centered palindrome corresponds to an odd-length one.
The algorithm
def manacher(s: str) -> list[int]:
# Transform: "abc" → "#a#b#c#"
t = "#" + "#".join(s) + "#"
n = len(t)
p = [0] * n # p[i] = radius of palindrome centered at i (in transformed string)
C = 0 # center of the rightmost palindrome found so far
R = 0 # right boundary of that palindrome (exclusive)
for i in range(n):
mirror = 2 * C - i
if i < R:
p[i] = min(p[mirror], R - i) # use mirror's radius, capped at boundary
# expand beyond the known radius
left, right = i - (p[i] + 1), i + (p[i] + 1)
while left >= 0 and right < n and t[left] == t[right]:
p[i] += 1
left -= 1
right += 1
# update the rightmost palindrome window
if i + p[i] > R:
C, R = i, i + p[i]
return p
def longestPalindrome(s: str) -> str:
p = manacher(s)
# find position with maximum radius
center = p.index(max(p))
radius = p[center]
# map back to original string
# in transformed string t, palindrome is t[center-radius .. center+radius]
# in original string: start = (center - radius) // 2
start = (center - radius) // 2
length = radius # radius in transformed = length in original
return s[start: start + length]
Frame-by-frame: s = "aba"
Transformed: t = "#a#b#a#" (indices 0-6)
p = [0,0,0,0,0,0,0] initially
i=0 '#': expand → no. p[0]=0. R=0, no update.
i=1 'a': i < R? 1<0? No. Expand: t[0]='#', t[2]='#' → match, p[1]=1.
t[-1] OOB → stop. p[1]=1. C=1, R=2.
i=2 '#': i < R? 2<2? No. Expand: t[1]='a', t[3]='b' → no. p[2]=0.
i=3 'b': i < R? 3<2? No. Expand: t[2]='#',t[4]='#'→match p[3]=1.
t[1]='a',t[5]='a'→match p[3]=2.
t[0]='#',t[6]='#'→match p[3]=3.
OOB → stop. p[3]=3. C=3, R=6.
i=4 '#': i<R? 4<6? Yes. mirror=2*3-4=2. p[2]=0. R-i=2. p[4]=min(0,2)=0.
Expand: t[3]='b',t[5]='a'→no. p[4]=0.
i=5 'a': i<R? 5<6? Yes. mirror=2*3-5=1. p[1]=1. R-i=1. p[5]=min(1,1)=1.
Expand: t[3]='b',t[7] OOB → stop. p[5]=1.
i=6 '#': i<R? 6<6? No. Expand: OOB. p[6]=0.
p = [0, 1, 0, 3, 0, 1, 0]
max p = 3 at center=3 (the 'b').
start = (3-3)//2 = 0, length = 3 → s[0:3] = "aba" ✅
The one idea to remember
The entire pattern in one sentence
Manacher's maintains the rightmost palindrome window [C, R]; for each new center i, it seeds p[i] with the mirror's cached radius (capped at the window boundary) and only does new character comparisons beyond that seed — making each character the expansion subject at most once, for O(n) total.
When to use Manacher's vs Expand-Around-Center
| Interview question | Recommended |
|---|---|
| "Find longest palindromic substring" | Expand Around Center (simpler, O(n²) usually fine) |
| "O(n) solution required explicitly" | Manacher's |
| Competitive programming | Manacher's |
| Count palindromes, DP on palindromes | Usually DP table or expansion is clearer |
In interviews, unless O(n) is explicitly asked for, expand-around-center is accepted and preferred for clarity. Know Manacher's as an upgrade you can mention.
Common traps
Watch out for these
- Forgetting the transformation. Without the
#separator, you need separate odd and even expansion logic. The transformation unifies them elegantly. - Using
i <= Rinstead ofi < R. The boundaryRis exclusive — use strict less-than. - Mapping back to original string incorrectly. In the transformed string,
center - radiusis the left#boundary. The original start index is(center - radius) // 2. - Treating
p[i]as half-length. In the transformed string,p[i]is the radius. The actual palindrome length in the original string is alsop[i](the transformation doubles lengths but radius = half of full palindrome length in transformed = actual length in original). Verify with a small example before your interview.
Remember this forever
Manacher's — 3 steps
- Transform: insert
#between all chars and at both ends. - Fill p[i]: seed with
min(p[mirror], R-i)ifi < R; then expand while chars match. - Update
[C, R]: ifi + p[i] > R, setC=i, R=i+p[i].
Map back: start = (center - radius) // 2, length = radius.
Shortcut for interviews: mention Manacher's exists, code Expand-Around-Center unless O(n) is required.
Check yourself
Why does the `#` transformation unify odd and even palindromes?
In the original string, odd-length palindromes center on characters and even-length ones center on gaps. After inserting # between every character, every gap becomes a # character — so gaps are now explicit characters too. All palindromes in the transformed string center on a character (which may be #). The algorithm only needs one case.
Why is `p[i]` in the transformed string equal to the palindrome length in the original string?
In the transformed string #a#b#a#, a palindrome of radius r spans 2r+1 characters. In this transformed string, r actual characters are interleaved with r separators, so r = number of original characters in the palindrome. This is why p[center] directly gives the original palindrome length.
Practice problems
| Problem | Difficulty | What to notice | Link |
|---|---|---|---|
| Longest Palindromic Substring | Medium | Manacher's gives O(n); expand-center is O(n²) but simpler | LC #5 |
| Palindromic Substrings (count) | Medium | Sum of all p[i] in transformed string gives total count | LC #647 |
Next up: String Reversal Tricks — how reversing substrings in-place solves rotation, word-order flip, and similar problems in O(n) time and O(1) space.