Manacher's Algorithm

Manacher's Algorithm

The classic palindrome problem, LeetCode 5. Longest Palindromic Substring, asks you to find the longest palindromic substring in a given string. The expand-around-center approach solves it in $O(n^2)$ time by trying every possible center and expanding outward. That is clean and interview-friendly, but there is a linear-time algorithm that solves the same problem in $O(n)$: Manacher's Algorithm. It works by reusing palindrome information already computed, avoiding redundant expansions entirely.

Preprocessing: Unifying Odd and Even Palindromes

Odd-length palindromes like "aba" center on a single character, while even-length palindromes like "abba" center between two characters. Handling both cases complicates the logic. Manacher's algorithm eliminates this distinction with a simple preprocessing trick. Insert a special character (typically '#') between every character and at both ends.

For example, "abba" becomes "#a#b#b#a#". Now every palindrome, whether originally odd or even, becomes an odd-length palindrome centered on a single position in the transformed string. The even palindrome "abba" becomes "#a#b#b#a#" centered on the middle '#' between the two 'b's, with an odd length of 9.

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

"abc" becomes "#a#b#c#" (length $2n + 1$). A palindrome radius of $r$ in the transformed string corresponds to a palindrome of length $r$ in the original string.

The Core Idea: Center C and Right Boundary R

Manacher's algorithm maintains two key variables as it scans left to right:

• C: the center of the palindrome whose right edge extends furthest to the right.
• R: that right edge (the index of the rightmost character reached by any palindrome found so far).

For each new position i, we build an array p[] where p[i] is the radius of the longest palindrome centered at i in the transformed string.

The key insight: if i < R, then i lies inside the palindrome centered at C. Its mirror position is mirror = 2 * C - i. Because palindromes are symmetric, p[mirror] gives us a lower bound for p[i]. We can initialize p[i] = min(p[mirror], R - i) and only expand beyond that. The min with R - i is needed because the mirror's palindrome might extend beyond the left edge of the palindrome centered at C, and we have no information past R.

If i >= R, we have no information and start with p[i] = 0, expanding from scratch.

After computing p[i], if i + p[i] > R, we update C = i and R = i + p[i].

Walked Example: "cbbd"

Let us trace through s = "cbbd". The transformed string is t = "#c#b#b#d#" (indices 0 through 8).

Initialize C = 0, R = 0, p = [0, 0, 0, 0, 0, 0, 0, 0, 0].

• i=0 (#): i >= R, so p[0] = 0. No expansion possible (left boundary). C=0, R=0.
• i=1 (c): i >= R, p[1] = 0. Try expand: t[0]='#' vs t[2]='#', which match, so p[1] = 1. t[-1] is out of bounds, stop. Update C=1, R=2.
• i=2 (#): i >= R, p[2] = 0. t[1]='c' vs t[3]='b', no match. C=1, R=2.
• i=3 (b): i >= R, p[3] = 0. t[2]='#' vs t[4]='#' match, so p[3] = 1. t[1]='c' vs t[5]='b', no match. Update C=3, R=4.
• i=4 (#): i < R (4 < 4 is false), so p[4] = 0. t[3]='b' vs t[5]='b' match, so p[4] = 1. t[2]='#' vs t[6]='#' match, so p[4] = 2. t[1]='c' vs t[7]='d', no match. Update C=4, R=6.
• i=5 (b): i < R (5 < 6). Mirror = 2*4 - 5 = 3, p[3] = 1. p[5] = min(1, 6-5) = 1. Try expand: t[3]='b' vs t[7]='d', no match. C=4, R=6.
• i=6 (#): i >= R, p[6] = 0. t[5]='b' vs t[7]='d', no match. Stays 0.
• i=7 (d): i >= R, p[7] = 0. t[6]='#' vs t[8]='#' match, so p[7] = 1. Out of bounds on right, stop. Update C=7, R=8.
• i=8 (#): i >= R, p[8] = 0. Out of bounds, stop.

Final p = [0, 1, 0, 1, 2, 1, 0, 1, 0]. The maximum is p[4] = 2 at index 4. The palindrome in the original string has length 2 and is centered at original index (4 - 1) / 2 = 1. Wait, let us compute the substring properly. The center in the transformed string is index 4, which corresponds to the '#' between the two 'b's. The original start index is (4 - 2) // 2 = 1 and the palindrome is s[1:3] = "bb". Correct.

Full Implementation

def manacher(s: str) -> str:
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    p = [0] * n
    C = R = 0

    for i in range(n):
        mirror = 2 * C - i
        if i < R:
            p[i] = min(p[mirror], R - i)

        # Attempt expansion
        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

        # Update center and right boundary
        if i + p[i] > R:
            C = i
            R = i + p[i]

    # Find the maximum radius and recover the substring
    max_radius = max(p)
    center = p.index(max_radius)
    start = (center - max_radius) // 2
    return s[start : start + max_radius]

The conversion back to the original string uses the fact that a radius of r in the transformed string corresponds to a palindrome of length r in the original string, starting at index (center - r) // 2.

Why It Is $O(n)$

The critical observation is that the right boundary R never moves left. It only increases. Each time we expand a palindrome past R, R advances by the number of new characters compared. A character can only contribute to expansion once (when R first passes over it). Since R can advance at most $2n + 1$ times total, the total number of character comparisons across all expansions is $O(n)$.

When i < R and we initialize p[i] from the mirror, no expansion is needed if the mirror palindrome fits entirely within [C - p[C], C + p[C]]. This is the "free" information that avoids the $O(n^2)$ trap of expand-around-center. We only pay for expansion when pushing R further right, and each position is pushed past at most once.

Application: Count All Palindromic Substrings

Consider LeetCode 647. Palindromic Substrings, which requires the total count of palindromic substrings. The expand-around-center approach solves this in $O(n^2)$, but with the Manacher radius array we can do it in $O(n)$.

Each entry p[i] in the transformed string represents a palindrome of radius p[i]. How many palindromic substrings does this account for? A position centered on an original character (odd index in the transformed string) with radius r contributes (r + 1) // 2 odd-length palindromes. A position centered on a '#' (even index) with radius r contributes r // 2 even-length palindromes. More simply, each center in the transformed string with radius p[i] contributes ceil(p[i] / 2) palindromic substrings to the total count, which equals (p[i] + 1) // 2.

def count_substrings(s: str) -> int:
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    p = [0] * n
    C = R = 0

    for i in range(n):
        mirror = 2 * C - i
        if i < R:
            p[i] = min(p[mirror], R - i)
        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
        if i + p[i] > R:
            C = i
            R = i + p[i]

    return sum((r + 1) // 2 for r in p)

Application: Shortest Palindrome

Take LeetCode 214. Shortest Palindrome: given a string s, find the shortest palindrome you can form by adding characters only to the front. The key insight is that you need the longest palindromic prefix of s. Whatever portion of s is already a palindrome starting from index 0, you keep; the remaining suffix gets reversed and prepended.

After running Manacher's on the transformed string, scan the radius array to find the rightmost center whose palindrome starts at position 0 in the original string. For a center at index c with radius p[c], the palindrome in the original string spans from (c - p[c]) // 2 to (c + p[c]) // 2 - 1. We need the one where the start is 0 and the length is maximized.

def shortest_palindrome(s: str) -> str:
    if not s:
        return s
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    p = [0] * n
    C = R = 0

    for i in range(n):
        mirror = 2 * C - i
        if i < R:
            p[i] = min(p[mirror], R - i)
        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
        if i + p[i] > R:
            C = i
            R = i + p[i]

    # Find longest palindromic prefix
    longest = 0
    for i in range(n):
        # Check if this palindrome starts at position 0 in original string
        if i - p[i] == 0:
            longest = max(longest, p[i])

    suffix = s[longest:]
    return suffix[::-1] + s

The condition i - p[i] == 0 checks that the palindrome in the transformed string starts at the very beginning (index 0 of t is '#', and (0) // 2 = 0 in the original string). The palindrome length in the original string is p[i], so we reverse everything after s[:longest] and prepend it.

Complexity

• Time: $O(n)$. Each position in the transformed string is visited once, and the total expansion work is bounded by the rightward movement of R.
• Space: $O(n)$ for the transformed string and the radius array p.

Recognizing this pattern

You're probably looking at Manacher's when:

• The problem wants the longest palindromic substring in strict $O(n)$, with input sizes around $10^5$ to $10^6$ where $O(n^2)$ is too slow.
• You need the full radius-at-every-center array, not just the single longest answer.
• The problem builds on top of palindrome preprocessing, such as counting all palindromic substrings, or prepending the shortest segment to make the whole string a palindrome.
• You've already written expand-around-center and TLE'd on the largest test cases.

Common templates:

• Longest palindromic substring in $O(n)$: run Manacher's, take the max radius, slice the original string. Example: Longest Palindromic Substring.
• Count palindromic substrings in $O(n)$: sum (p[i] + 1) // 2 across the radius array. Example: Palindromic Substrings.
• Shortest palindrome by prepending: find the longest palindrome anchored at index 0, reverse the suffix beyond it. Example: Shortest Palindrome.
• Palindrome partitioning with $O(1)$ checks: precompute Manacher's radii, answer "is s[l..r] a palindrome?" in constant time. Example: Palindrome Partitioning IV.