Manacher's Algorithm — Longest Palindromic Substring in O(n)

LeetCode 5 — Longest Palindromic Substring — is one of the most common interview problems. The O(n^2) expand-around-centre solution passes most judges. Manacher's O(n) solution demonstrates you understand linear string algorithms at a structural level, not just memorised patterns.

Manacher (1975) is not widely taught in undergraduate curricula, which means knowing it distinguishes you. The underlying technique — maintaining a rightmost boundary and exploiting mirror symmetry — is the exact same structural insight as KMP and Z-algorithm. Once you see this pattern, you recognise it everywhere.

The Even/Odd Problem and the Transformation

Palindromes come in two flavours: odd-length ('aba') and even-length ('abba'). Handling both cases separately doubles code complexity. Manacher's standard trick: insert a separator character between every character (and at boundaries) to convert all palindromes to odd-length.

Original: 'abba' Transformed: '#a#b#b#a#'

Now every palindrome in the original maps to an odd-length palindrome in the transformed string. '#b#b#' is the palindrome for 'bb'. '#a#b#b#a#' is the palindrome for 'abba'. We only need to handle one case.

def transform(s: str) -> str:
    return '#' + '#'.join(s) + '#'

print(transform('abba'))   # '#a#b#b#a#'
print(transform('racecar'))# '#r#a#c#e#c#a#r#'

The P Array — Palindrome Radii

For the transformed string T, we compute P[i] = the radius of the longest palindrome centred at i (not counting the centre itself). So P[i] = k means T[i-k..i+k] is a palindrome.

The length of the corresponding original palindrome is P[i] (the separator characters cancel out).

For T = '#a#b#b#a#': - P[0]=0 ('#') - P[1]=1 ('#a#') - P[2]=0 ('a') - P[3]=3 ('#a#b#b#a#') ← full string - P[4]=3 (same, centre is '#' between two b's) - etc.

Manacher's Algorithm — Full Implementation

Manacher maintains a 'mirror window' [l, r] — the palindrome with the rightmost boundary seen so far (centre c, right edge r). For each i, if i < r, initialise P[i] from the mirror position (2*c - i). Then try to expand.

def manacher(s: str) -> str:
    # Transform to handle even/odd uniformly
    T = '#' + '#'.join(s) + '#'
    n = len(T)
    P = [0] * n
    c = r = 0  # centre and right boundary of rightmost palindrome

    for i in range(n):
        mirror = 2 * c - i  # mirror of i around c

        if i < r:
            P[i] = min(r - i, P[mirror])

        # Try to expand around i
        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 rightmost palindrome boundary
        if i + P[i] > r:
            c, r = i, i + P[i]

    # Find maximum in P
    max_len, centre = max((v, i) for i, v in enumerate(P))
    start = (centre - max_len) // 2
    return s[start : start + max_len]

print(manacher('babad'))       # 'bab' or 'aba'
print(manacher('cbbd'))        # 'bb'
print(manacher('racecar'))     # 'racecar'
print(manacher('abacabadabacaba')) # 'abacabadabacaba'

Why it's O(n) — The Rightmost Boundary Argument

The r pointer only ever moves right — never decreases. Each time we expand (the while loop), r increases. So the total number of expansions across all iterations is at most n. All other operations per iteration are O(1). Total: O(n).

This is the same argument as KMP (pointer only moves forward) and Z-algorithm (r only moves right). Recognising this pattern is key to understanding linear string algorithms.

Finding All Palindromic Substrings

Manacher computes all palindrome radii in one pass, so you can use P to answer queries like 'is s[l..r] a palindrome?' in O(1) after O(n) preprocessing.

def all_palindrome_lengths(s: str) -> list[int]:
    """Return length of longest palindrome centred at each position."""
    T = '#' + '#'.join(s) + '#'
    n = len(T)
    P = [0] * n
    c = r = 0
    for i in range(n):
        if i < r:
            P[i] = min(r - i, P[2*c - i])
        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] > r:
            c, r = i, i + P[i]
    # Extract only original positions (every other entry in P)
    return [P[2*i+1] for i in range(len(s))]  # odd centres

print(all_palindrome_lengths('abacaba'))
# [1, 3, 1, 7, 1, 3, 1] — longest palindrome at each centre

Frequently Asked Questions