Manacher's Algorithm: One Linear Pass, Every Palindrome Found

You want the longest palindromic substring. You write the obvious thing: for each center, expand outward until characters stop matching. It works. It passes the examples. Then n = 10^5 lands on your submission and the judge prints "Time Limit Exceeded" with the quiet contempt of a system that has seen this exact code approximately ten thousand times.

Manacher's algorithm does the same job in O(n). Published by Glenn Manacher in the Journal of the ACM in 1975, it does something that feels like cheating: while expanding a palindrome at a new center, it checks whether a previously computed palindrome already tells you the answer. Often it does, and the work gets skipped entirely. The net result is that every character gets examined only a bounded number of times total, across all n centers.

The mental model: maintain the rightmost palindrome you've fully expanded, and use its symmetry to initialize every new center for free.

Reach for Manacher's when the problem involves palindromic substrings and n is large enough that O(n²) won't clear the time limit, or when you need O(1) palindrome queries after a one-time O(n) precomputation.

Why Expand-Around-Center Costs O(n²)

The naive approach is correct. Worth understanding first, because Manacher's is just a smarter version of it.

For each center position (there are 2n-1 of them, counting gaps between characters for even-length palindromes), you expand outward one character at a time until a mismatch. Best case: the string has no repeated characters, every expansion terminates immediately, O(n) total. Worst case: "aaaaaaa" and every center expands to the wall. O(n²). That's the case that gets you rejected.

Manacher eliminates the worst case without changing the outer structure. The loop still visits every center. What changes is that some centers start from a nonzero radius instead of zero, so their expansion has less work to do. Sometimes zero work.

The Transformation That Unifies Odd and Even

Palindromes come in two flavors: odd-length ("racecar", centered on a character) and even-length ("abba", centered on the gap). Handling both in one pass with the same code requires a classic trick.

Insert a '#' between every adjacent pair of characters, and add sentinel characters '@' and '$' at the ends.

original:    r  a  c  e  c  a  r
transformed: @ # r # a # c # e # c # a # r # $
position:    0 1 2 3 4 5 6 7 8 9 ...

The string transformation: every palindrome becomes odd-length in the transformed string Inserting '#' unifies odd and even palindromes. '@' and '$' are mismatched sentinels that stop expansion at boundaries without a bounds check.

For a string of length n, the transformed string t has length 2n+3. Every palindrome in the original string becomes odd-length in t. The '#' characters represent even-length palindrome centers; letter characters represent odd-length centers. One case to handle.

The sentinels '@' and '$' serve a separate purpose: they guarantee the expansion loop never steps out of bounds. Since '@' != '$' and neither appears in the '#'-separated letter strings, any expansion that hits a sentinel stops immediately. No bounds checking needed inside the hot loop.

The Radius Array

For each position i in t, define p[i] as the radius of the palindrome centered there. Radius 0 means the center alone (or no palindrome at all, for a '#' position with no matching neighbors).

t:    @ # a # a # b # $
p:    0 0 1 2 1 0 1 0 0

The critical connection back to the original: the length of the palindrome in the original string equals p[i] exactly. For the '#' at position 3 above, p[3] = 2, which is "aa" of length 2. For the 'a' at position 2, p[2] = 1, which is "a" of length 1.

Starting index in the original string for a palindrome centered at position i with radius p[i]:

start_in_original = (i - p[i]) / 2

Integer division. Works regardless of whether i is a letter or '#' position, because i and p[i] always have the same parity: letter positions always have odd p[i], '#' positions always have even p[i] (or zero).

The p[] radius array filled in for "aacecaaa" with bar visualization p[i] for "aacecaaa". The tallest bar is at center i=8 ('e') with p[8]=7, meaning the palindrome "aacecaa" of length 7 starts at (8-7)/2 = 0.

The Mirror Insight

Here is the key idea. Suppose you've already expanded a palindrome centered at position c, extending to position r on the right (and symmetrically to l = 2c - r on the left). You're now computing p[i] for some new position i between c and r.

Because the big palindrome is symmetric around c, everything to the right mirrors everything to the left. The mirror of i is j = 2c - i.

You already know p[j]. What does it tell you about p[i]?

The mirror insight: j is the mirror of i through center c, inside the rightmost palindrome When i is inside the rightmost palindrome [l, r], its mirror j = 2c-i tells you the minimum radius at i. Three cases determine whether you can skip expansion entirely.

If p[j] < r - i: the j-palindrome fits entirely inside the big palindrome, well clear of its left boundary. By symmetry, the i-palindrome fits entirely inside the big palindrome too, well clear of the right boundary. So p[i] = p[j]. No expansion. Done.

If p[j] > r - i: the j-palindrome extends past the left boundary l. Past that boundary you have no symmetry guarantee. Initialize p[i] = r - i and expand from r.

If p[j] == r - i: the j-palindrome exactly touches l. Initialize p[i] = r - i and try to expand, because the characters beyond r are unknown territory.

The three cases unify into one line: set p[i] = min(r - i, p[mirror]) when i is inside the rightmost palindrome, then always attempt expansion.

p[i] = min(r - i, p[2*c - i])  if i < r  else  0
while t[i + p[i] + 1] == t[i - p[i] - 1]:
    p[i] += 1
if i + p[i] > r:
    c, r = i, i + p[i]

When expansion succeeds, you've found a new rightmost palindrome and update c and r.

Why Manacher's Algorithm Is O(n)

The expansion loop looks like it might be quadratic. It isn't, and the proof is short enough to actually understand.

Watch r over the entire run. r is the right boundary of the rightmost palindrome seen so far.

r starts at 0.
Every time the while loop executes one iteration, r increases by exactly 1. (A successful comparison extended the palindrome, which means the new boundary is one further right.)
r never decreases.
r is bounded above by 2n+3 (the length of t).

Since r can increase at most 2n+3 times total, the while loop executes at most 2n+3 iterations across all n centers combined. Everything else in the outer loop is O(1). The algorithm is O(n) overall.

The monotone-r argument: r never goes backwards, so total expansion steps are bounded by 2n+3 r is a monotone counter. It can advance at most 2n+3 times total. That's the entire expansion budget for all n centers combined.

This is a classic amortized analysis: per-center cost looks variable, but the total budget is fixed. Any center that spends a lot on expansion earns future centers a free pass via the mirror lookup.

Core Operations

Operation	Time	Space	Notes
Build p[] array	O(n)	O(n)	The full precomputation
Longest palindromic substring	O(n)	O(n)	Scan p[] for max after build
Count all palindromic substrings	O(n)	O(n)	Sum of (p[i]+1)/2 after build
Is s[l..r] a palindrome?	O(1)	O(1)	After O(n) build; check center

Building p[] is the entire algorithm. Everything else is a one-line post-processing step.

Why O(n) time: the amortized argument above. r marches right at most n times total.

Why O(n) space: the transformed string t has length 2n+3, and the p[] array has the same length.

Why O(1) palindrome queries after preprocessing: for any substring s[l..r], compute whether it's a palindrome by checking the palindrome centered at its midpoint in the transformed string. The center in t is l + r + 2 (with the '@#' prefix). The check is p[l + r + 2] >= r - l + 1. Both sides computable in O(1).

Counting palindromic substrings: each position i in t contributes floor((p[i] + 1) / 2) distinct palindromic substrings in the original. For a letter position with p[i] = 2k+1, that's k+1 palindromes (lengths 1, 3, ..., 2k+1). For a '#' position with p[i] = 2k, that's k palindromes (lengths 2, 4, ..., 2k). The formula (p[i]+1)//2 covers both because letter positions always have odd p[i] and '#' positions always have even p[i].

One Structure, Every Language

All fourteen implementations follow the same structure: build the transformed string, compute the p[] array with the two-pointer invariant, then post-process. Each shows longestPalindrome (returns the longest palindromic substring) and countPalindromes (returns the count of all palindromic substrings).

def longest_palindrome(s: str) -> str:
    t = "@#" + "#".join(s) + "#$"
    n = len(t)
    p = [0] * n
    c = r = 0
    for i in range(1, n - 1):
        mirror = 2 * c - i
        if i < r:
            p[i] = min(r - i, p[mirror])
        while t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1
        if i + p[i] > r:
            c, r = i, i + p[i]
    max_len, center = max((p[i], i) for i in range(1, n - 1))
    start = (center - max_len) // 2
    return s[start : start + max_len]


def count_palindromes(s: str) -> int:
    t = "@#" + "#".join(s) + "#$"
    n = len(t)
    p = [0] * n
    c = r = 0
    for i in range(1, n - 1):
        mirror = 2 * c - i
        if i < r:
            p[i] = min(r - i, p[mirror])
        while t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1
        if i + p[i] > r:
            c, r = i, i + p[i]
    return sum((p[i] + 1) // 2 for i in range(1, n - 1))

What Problems It Solves

Manacher's p[] array gives you a complete palindrome map of the string, computed in one pass. Problems that benefit from this map fall into a few classes.

Longest palindromic substring. The direct application. Scan p[] for the maximum. O(n) total.

Counting palindromic substrings. Sum (p[i]+1)//2 over all positions in the transformed string. This is the formula behind LeetCode 647.

O(1) palindrome queries. After building p[], answer "is s[l..r] a palindrome?" in constant time. The center of s[l..r] in the transformed string is at position l + r + 2 (0-indexed, with the '@#' prefix). If p[l + r + 2] >= r - l + 1, the answer is yes.

Palindromic prefix length. Find the largest L such that the palindrome at the center covering position 1 of t reaches all the way back to position 1. That gives the longest palindromic prefix. Used in the shortest-palindrome-by-prepending problem.

Palindrome partitioning DP speedup. The standard partitioning DP checks "is s[l..r] a palindrome?" for each (l, r) pair. With precomputed p[], each check drops to O(1), shaving a log factor off the naive approach.

Recognizing the Pattern

Two signals almost always appear together: the word "palindrome" in the problem and a constraint that makes O(n²) too slow. If you see n up to 10^5 or 10^6 with a time limit that rules out quadratic work, Manacher's is the tool.

The subtler signal is any problem that needs to check many different substrings for palindromicity. If the solution would require calling isPalindrome(l, r) inside a loop, precompute the p[] array and make each call O(1) instead.

Worked Example 1: Count All Palindromic Substrings (LeetCode 647)

Problem: Given a string s, return the number of palindromic substrings it contains. "a" counts as one palindrome, "aa" gives three ("a", "a", "aa").

Why Manacher fits: You need every palindrome, not just the longest. The naive approach double-loops over centers and radii: O(n²). Manacher computes every radius in O(n), then the count is a single pass over p[].

How to extract it: After building p[], sum (p[i]+1)//2 for all positions i in [1, n-1] of the transformed string (skipping sentinel positions 0 and n-1).

For s = "aab":

t:  @ # a # a # b # $
p:  0 0 1 2 1 0 1 0 0
contributions: 0 + 1 + 1 + 1 + 0 + 1 + 0 = 4

Palindromes: "a" (index 0), "a" (index 1), "aa", "b". Count = 4. Correct.

Worked Example 2: Shortest Palindrome by Prepending (LeetCode 214)

Problem: Given s, find the shortest palindrome you can create by prepending characters to the front. For s = "aacecaaa", the answer is "aaacecaaa".

Why Manacher fits: Any palindrome formed by prepending to s has the form rev(suffix) + s. To minimize length, maximize the palindromic prefix of s. Then prepend the reverse of the remaining suffix.

How to extract the palindromic prefix length: Build the p[] array. Scan from the center of the full string toward position 1. The largest center i such that p[i] == i - 1 gives the longest palindromic prefix. (It means the palindrome reaches all the way back to position 1 of t, which is the first character.)

For s = "aacecaaa" (length 8), the longest palindromic prefix is "aacecaa" (length 7). The center in t at position 8 ('e') has radius 7, and 8 - 7 = 1 satisfies p[i] == i - 1. The remaining suffix is "a". Prepend "a" to get "aaacecaaa". Correct.

(KMP also solves LeetCode 214 by concatenating s + "#" + reverse(s) and reading the failure function. If you already have the Manacher array for other reasons, the palindromic prefix is a free read.)

The Non-Obvious Bug You Will Write Once

Do not use '#' as the separator character if '#' can appear in the input.

For inputs that can contain any printable ASCII, '#' as a separator creates collisions. The palindrome "a#a" in the original string produces the transformed substring "a###a", where the middle '#' looks like a separator instead of content. The algorithm will silently give wrong answers and you will not figure out why for longer than is comfortable to admit.

The fix: use characters guaranteed absent from the input. For ASCII strings, \x01 and \x02 work. For Unicode, use code points from the private use area, or work with integer arrays and use -1 as the separator sentinel and -2/-3 for the outer sentinels.

The second bug is off-by-one in the max search. The loop scanning p[] for the maximum must run from index 1 to n-2 inclusive, skipping both sentinels. A loop that runs 0 to n-1 reads p[0] and p[n-1] (always 0) and wastes a comparison. More importantly, if the original string is empty the transformed string has length 3 and you must handle that before calling the algorithm.

Recap

Manacher runs in O(n) by maintaining center c and right boundary r of the rightmost palindrome, using the mirror lookup to initialize each new center.
The monotone-r amortized argument: r never decreases, so total expansion steps across all n centers is at most 2n+3.
Transform with "@#s[0]#s[1]#...#s[n-1]#$" to unify odd and even palindromes. Every palindrome in t has odd length.
p[i] in the transformed string equals the palindrome length in the original string.
Longest palindrome: argmax(p[]). Start = (center - max_len) / 2. Length = max_len.
Count all palindromic substrings: sum (p[i]+1)//2 over all non-sentinel positions.
O(1) palindrome query for s[l..r] after preprocessing: p[l + r + 2] >= r - l + 1.
Separator collision is a silent bug. Use characters that cannot appear in the input.
The algorithm exists in two forms: the transformed-string approach shown here, and the two-array d1/d2 approach (separate odd and even radii, no transformation). Both are O(n).

If you want to practice explaining this under pressure, not just implementing it at a quiet keyboard, SpaceComplexity runs voice-based mock interviews with rubric-based feedback across the dimensions that actually matter: problem-solving, communication, code quality, and testing. The algorithm is the easy part. Talking through the three mirror cases while someone is watching is the part that takes practice.

For related structural ideas, the suffix array and suffix tree articles cover other linear-time string preprocessing algorithms that pair well with Manacher's in problems that need both palindrome and substring queries.

The KMP string matching article covers the other canonical linear-time string algorithm, with a similar amortized analysis built on a monotonically advancing pointer.