Problem Statement

Manacher's Algorithm

A palindrome is a string that reads the same forwards and backwards, like "aba" or "noon". Our job is to find the longest palindrome hiding inside a string. The slow way is to stand at every letter and grow outward, checking left and right, until the two sides stop matching. That works, but it redoes a lot of comparisons. Manacher's algorithm is the fast way: it does the same growing idea, but it remembers the palindromes it already found and reuses that memory to skip work it has already done. The result is O(n) time, meaning the work grows in a straight line with the length of the string, instead of O(n squared), which grows much faster.

hardStringStringsTime: O(n) · Space: O(n)

Signals to notice

find all palindromes centered at each position in O(n)mirror property within known palindromes

Brute force first

Expand around each center — O(n²).

The key insight

Manacher's: use known palindrome radii to skip redundant expansion. Maintain rightmost boundary and center. O(n).

Trace it on `s="cbbd" → t="#c#b#b#d#" (n=9)`

i=1 ('c'): 1<right(0) false; expand p[1]=1 (t[2]='#'==t[0]='#'); 1+1>0 → center=1,right=2
i=3 ('b'): 3<right(2) false; expand p[3]=1 (t[4]='#'==t[2]='#'); 3+1>2 → center=3,right=4
i=4 ('#'): 4<right(4) false; expand p[4]=2 (t[5]='b'==t[3]='b', t[6]='#'==t[2]='#'); 4+2>4 → center=4,right=6
i=5 ('b'): 5<right(6) true, mirror=3 → p[5]=min(6-5,p[3]=1)=1; expand fails (t[7]='d'≠t[3]='b'); 5+1>6 false → center,right unchanged
i=7 ('d'): 7<right(6) false; expand p[7]=1 (t[8]='#'==t[6]='#'); 7+1>6 → center=7,right=8
skipped i=0,2,6,8 all give p=0; final p=[0,1,0,1,2,1,0,1,0]
max_len=2 at ci=4; start=(4-2)//2=1 → s[1:3]="bb"

What must stay true

If position i is within a known palindrome, the mirror's radius provides a starting point. Only expand beyond the known boundary.

Shape of the loop

t = "#" + interleave(s) + "#"; n = len(t); p[0..n) = 0; center = right = 0
for i in 0..n:
    if i < right: p[i] = min(right - i, p[2*center - i])          # reuse mirror radius
    while i+p[i]+1 < n and i-p[i]-1 >= 0 and t[i+p[i]+1] == t[i-p[i]-1]:
        p[i] += 1                                                  # expand beyond known boundary
    if i + p[i] > right: center, right = i, i + p[i]               # extend rightmost palindrome
maxLen = max(p); ci = index_of(maxLen); start = (ci - maxLen) // 2
return s[start : start + maxLen]

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not handling boundary cases when the mirror's palindrome extends beyond the rightmost boundary.

Strings Pattern