Manacher’s Algorithm
Manacher’s algorithm finds the longest palindromic substring of a length-
nstring in O(n) time — beating the naive O(n²) “expand around every center” approach by reusing palindrome information from previously processed centers. It builds an arrayP[i]whereP[i]is the palindromic radius centered at positioni. The algorithm’s key trick is the#separator: insert a unique non-alphabet character between every pair of original characters (and at both ends), turning even-length palindromes into odd-length ones in the transformed string so that a single uniform “expand around center” treatment handles both parities. Manacher’s 1975 paper introduced the algorithm in the more limited form of “smallest initial palindromic prefix”; the modern presentation as a general longest-palindromic-substring algorithm is folkloric, attributed variously to Apostolico-Galil and to Jeuring.
1. Intuition — Use the Symmetry You Already Found
A palindrome reads the same forwards and backwards: racecar, abba, level. To find the longest palindromic substring of some text s, the brute-force approach is to try every (start, end) pair — that’s O(n²) candidates, and verifying each is O(n), for O(n³) total. The classic improvement, “expand around every center,” picks each of the 2n − 1 possible centers (every character is an odd-length center, every gap between adjacent characters is an even-length center) and walks outward as long as s[center − k] == s[center + k]. That’s O(n²) — much better, and frankly good enough for almost every interview problem.
Manacher noticed that this O(n²) is wasteful in a specific way: if you’ve already discovered a long palindrome centered at some position c, then for any position i inside that palindrome, the structure to the right of c mirrors the structure to the left. So the palindrome centered at i should initially be at least as long as the palindrome centered at i’s mirror image i' = 2c − i — provided both lie strictly inside the outer palindrome. We can copy P[i'] → P[i] “for free” and only need to do new comparisons if the mirror palindrome happens to extend past the outer palindrome’s right edge.
The real-world analogy: imagine you’ve assembled half of a perfectly symmetric jigsaw puzzle (the left half). The right half must mirror it. So when you start placing pieces on the right, you don’t need to study each one in isolation — you just check whether it matches the corresponding left-side piece. You only need genuine new analysis when you reach a piece that has no left-side counterpart yet (i.e., one that extends past the symmetric region you’ve already verified).
The same mirror trick powers the Z-Algorithm ([l, r] window of the rightmost match) and Knuth-Morris-Pratt’s failure-function reuse. Manacher is essentially the palindrome-specialised version of that family.
2. The # Separator Trick
The first hurdle: palindromes come in odd length (aba, single character center) and even length (abba, no character at the center — the center sits between two characters). These look like different cases and you’d otherwise need two parallel arrays — P_odd[i] for odd-length palindromes centered at index i, and P_even[i] for even-length palindromes centered between i and i+1. Manacher’s elegant solution is to transform the input so all palindromes become odd.
Insert a fresh character # (or any character not in the alphabet) between every pair of original characters and at both ends:
original: a b a b a
transformed: # a # b # a # b # a #
^ index 5: center of "ababa" in original
The transformed string has length 2n + 1 for an n-character original. Now every even-length palindrome in the original becomes an odd-length palindrome in the transformed string (its center is one of the inserted #s); every odd-length palindrome stays odd-length but with #s interleaved (its center is an original character).
For example, "abba" (even, length 4) becomes #a#b#b#a#; the longest palindromic substring centered at index 4 (the middle #) is #a#b#b#a# (length 9 in the transformed string). Map it back: the radius P[4] = 4 (4 characters on each side of the center, ignoring the center itself), and the palindrome length in the original string is exactly P[4] = 4. By design.
For "aba" (odd, length 3), the transformed string is #a#b#a#; centered at index 3 (the original b), the longest palindrome is the entire transformed string (length 7). Radius P[3] = 3, original length P[3] = 3. Also by design.
Why this works. A palindrome in the transformed string has alternating # and original characters. Removing the #s yields a palindrome in the original string of length equal to the radius P[i] in the transformed string. This is the central convenience: P[i] in the transformed string = length of the corresponding palindrome in the original string, regardless of parity. One uniform array, one uniform algorithm.
The choice of # is arbitrary — any character not in the alphabet works. For binary strings use # or any non-bit character; for arbitrary-byte strings pick a character demonstrably absent. If you can’t guarantee absence, pick a sentinel like chr(max(map(ord, s)) + 1) or use a tagged-pair representation (a list of (char, original-vs-separator) tuples) to side-step the issue.
3. Tiny Worked Example
Take s = "abaab" (length 5). Transform to t = "#a#b#a#a#b#" (length 11).
We compute P[i] for each i in t:
| i | t[i] | P[i] | Palindrome centered at i (in t) | Maps to (in s) |
|---|---|---|---|---|
| 0 | # | 0 | # | "" (length 0) |
| 1 | a | 1 | #a# | a (length 1) |
| 2 | # | 0 | # | "" |
| 3 | b | 1 | #b# | b (length 1) |
| 4 | # | 0 | # | "" |
| 5 | a | 3 | #a#a#a# ? | wait — is aaa a substring of s? |
Pause. s = "abaab"; positions 2,3,4 are a, a, b. So s[0..3] = "abaa" which contains "aba" (positions 0–2) but not "aaa". Let me recompute carefully.
Transformed string indices:
i: 0 1 2 3 4 5 6 7 8 9 10
t: # a # b # a # a # b #
s-pos: 0 1 2 3 4
So t[5] = a corresponds to s[2] = a. The palindrome centered at t[5]:
- Radius 1:
t[4..6] = "#a#"✓ - Radius 2:
t[3..7] = "b#a#a". Endpointsbandadiffer. ✗
So P[5] = 1, mapping to palindrome of length 1 in s ("a"). I miscounted above. Continuing carefully:
| i | t[i] | P[i] | Palindrome in t | Length in s |
|---|---|---|---|---|
| 0 | # | 0 | # | 0 |
| 1 | a | 1 | #a# | 1 (a) |
| 2 | # | 0 | # | 0 |
| 3 | b | 1 | #b# | 1 (b) |
| 4 | # | 0 | # | 0 |
| 5 | a | 1 | #a# | 1 (a) |
| 6 | # | 3 | b#a#a#b wait check: t[3..9]=“b#a#a#b”, palindrome around t[6]=# → t[5]=a, t[7]=a ✓; t[4]=#, t[8]=# ✓; t[3]=b, t[9]=b ✓; so radius 3 ✓ | 2 (aa) |
| 7 | a | 1 | #a# | 1 (a) |
| 8 | # | 0 | # | 0 |
| 9 | b | 1 | #b# | 1 (b) |
| 10 | # | 0 | # | 0 |
Wait, I missed a palindrome. s = "abaab" contains "aba" (positions 0–2). That should give P[3] (centered on the original b at t[3]) a radius of 3, not 1. Let me re-examine t around index 3:
t: # a # b # a # a # b #
i: 0 1 2 3 4 5 6 7 8 9 10
Centered at t[3] = b: radius 1 means t[2..4] = "#b#" ✓; radius 2 means t[1..5] = "a#b#a" → endpoints a == a ✓, all interior matches; radius 3 means t[0..6] = "#a#b#a#" → endpoints # ✓. So P[3] = 3! That maps back to the palindrome of length 3 in s, namely s[0..2] = "aba". Let me also recheck P[7] (centered on t[7] = a): radius 1 = "#a#" ✓; radius 2 = t[5..9] = "a#a#b" → endpoints a vs b ✗. So P[7] = 1.
Corrected table:
| i | P[i] | Palindrome in s | Length in s |
|---|---|---|---|
| 0 | 0 | — | 0 |
| 1 | 1 | a | 1 |
| 2 | 0 | — | 0 |
| 3 | 3 | aba | 3 |
| 4 | 0 | — | 0 |
| 5 | 1 | a | 1 |
| 6 | 3 | aa (centered between) | 3? wait, P[6]=3 maps to length 3? Let me re-check. |
Actually P[6] = 3 means radius 3, so the palindrome in t is length 2·3 + 1 = 7 characters: t[3..9] = "b#a#a#b". Mapping back to s (strip #s): "baab", length 4. Hmm, but I said the length in s equals P[i]. Let me re-derive that mapping.
A palindrome in t of radius r has 2r + 1 total characters, of which r are #s (the alternating ones) on each side and the center can be either # or original. The non-# characters number r (if center is #) or r + 1 (if center is original character — but then r must be even because #s alternate strictly). Hmm — so the length in s is r regardless of whether the center is # or original. Let me recheck P[3] = 3: r = 3, length in s = 3. The palindrome "aba" has length 3. ✓. And P[6] = 3: length in s = 3? But "baab" has length 4. Something’s off.
Reading the cp-algorithms.com note carefully: “the palindrome length in the original string equals P[i] when the convention is that P[i] is the radius not counting the center itself, but counting only on one side.” Let me redo with this convention.
With one-sided radius P[i] (= number of characters strictly to one side of the center that match the symmetric ones), the palindrome in t has length 2·P[i] + 1 and the corresponding palindrome in s has length P[i] (you can prove this by counting non-# characters: ⌈P[i]/2⌉ on each side plus possibly the center character itself, all summing to P[i]).
So the corrected centers-and-lengths-in-s for our example:
P[3] = 3→ length 3 ins→ “aba” ✓P[6] = 3→ length 3 ins. But what 3-character palindrome is centered “betweens[2]ands[3]”? That’d be a palindrome likes[1..3]= “baa” — not a palindrome. SoP[6] = 3is wrong.
Let me painstakingly recompute P[6]. t[6] = #. Radius 1: t[5..7] = "a#a" — endpoints a and a match ✓. Radius 2: t[4..8] = "#a#a#" — endpoints # and # match ✓. Radius 3: t[3..9] = "b#a#a#b" — endpoints b and b match ✓. Radius 4: t[2..10] = "#b#a#a#b#" — endpoints # and # match ✓. Radius 5: t[1..11] — but t only has indices 0..10, so this is out of bounds. So P[6] = 4 (we matched up through radius 4 and ran out of string, not because of a mismatch).
Length in s = 4 → “baab” — s[1..4] = "baab" ✓. That’s the longest palindromic substring of s = "abaab".
Lesson learned: even on a tiny example, carefully track the convention. The slip above (P[6] = 3 initially) is exactly the kind of off-by-one that derails Manacher implementations. The relationship is length_in_s = P[i] when P[i] is defined as the maximum k such that t[i-k..i+k] is a palindrome. Some references define P[i] as the full length 2k + 1 of that palindrome — under that convention, length_in_s = (P[i] - 1) / 2. Always state the convention explicitly.
Final corrected table for s = "abaab":
i: 0 1 2 3 4 5 6 7 8 9 10
t: # a # b # a # a # b #
P[i]: 0 1 0 3 0 1 4 1 0 1 0
Maximum P[i] is P[6] = 4, achieved at the gap between s[1] and s[2], giving the palindrome s[1..4] = "baab". The starting position in s is (i - P[i]) // 2 = (6 - 4) // 2 = 1, and the length is P[i] = 4. ✓
4. The Algorithm
Maintain two indices c and r:
cis the center of the rightmost-extending palindrome found so far.ris the right boundary (exclusive) of that palindrome, i.e.,r = c + P[c].
For each new index i:
-
Mirror trick. If
i < r, reflectiacrosscto getmirror = 2c − i. The palindrome centered atmirrorhas known radiusP[mirror]. InitialiseP[i] = min(r − i, P[mirror]). Theminhandles the edge case where the mirror palindrome extends pastr— we only know aboutr − icharacters worth of agreement. -
Attempt to extend. Try to extend the palindrome at
ioutward: whilet[i + P[i] + 1] == t[i − P[i] − 1], incrementP[i]. (Careful with bounds.) -
Update
(c, r). Ifi + P[i] > r, setc = i, r = i + P[i].
The bounds on extension are exactly what makes this O(n): each successful extension pushes r strictly to the right, and r ≤ 2n + 1, so the total extension work across all iterations is O(n).
5. Pseudocode
Manacher(s):
# transform: insert '#' between every pair, and at both ends
t := "#"
for c in s:
t += c + "#"
n := length(t)
P := array of n zeros
c := 0 # center of current rightmost palindrome
r := 0 # right boundary (exclusive)
for i in 0 .. n-1:
if i < r:
mirror := 2·c − i
P[i] := min(r − i, P[mirror])
# try to extend
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] := P[i] + 1
if i + P[i] > r:
c := i
r := i + P[i]
# find max
best_i := argmax_i P[i]
start_in_s := (best_i − P[best_i]) // 2
length := P[best_i]
return s[start_in_s : start_in_s + length]
6. Python Implementation
def manacher(s: str) -> str:
"""Return a longest palindromic substring of `s` in O(len(s)) time.
If multiple palindromes share the maximum length, returns the leftmost.
"""
if not s:
return ""
# Transform: insert sentinel '#' between every pair of characters and
# at both ends. Pick a sentinel known to be absent from s; if '#' could
# appear, fall back to a fresh code point.
sep = "#"
if sep in s:
sep = chr(max(map(ord, s)) + 1)
t = sep + sep.join(s) + sep
n = len(t)
P = [0] * n # P[i] = palindromic radius centered at t[i]
c = r = 0 # center and right boundary of the rightmost palindrome
for i in range(n):
if i < r:
mirror = 2 * c - i
# Initial radius = the smaller of (a) what fits in the current
# window [c - (r-c) + 1, r-1], i.e. r - i, and (b) the known
# mirror radius.
P[i] = min(r - i, P[mirror])
# Try to extend outward by character comparison.
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 the rightmost palindrome's center if we just pushed past r.
if i + P[i] > r:
c, r = i, i + P[i]
# Locate the best palindrome.
best_i = max(range(n), key=lambda i: P[i])
length = P[best_i]
start = (best_i - length) // 2
return s[start:start + length]
# Sanity checks:
assert manacher("abaab") == "baab"
assert manacher("babad") in ("bab", "aba")
assert manacher("cbbd") == "bb"
assert manacher("a") == "a"
assert manacher("") == ""
assert manacher("forgeeksskeegfor") == "geeksskeeg"The sentinel-pickup logic in lines 8–10 is a robustness detail many implementations omit. If your input is ASCII text, # is almost always safe; for arbitrary inputs (binary, internationalised text), the fallback matters.
7. Complexity
7.1 Time
The outer for loop runs n = 2|s| + 1 times. The inner while loop’s total iterations across the entire algorithm is bounded by n: each iteration of the while loop strictly increases r by 1 (because the new palindrome at i reaches strictly further right than any previous one — otherwise the min(r - i, P[mirror]) initialisation would have given the answer without entering the while loop), and r is bounded above by n.
So total work: O(n) outer iterations + O(n) cumulative while iterations = O(n), where n = 2|s| + 1. In terms of the original input length |s|, that’s also O(|s|).
This is an aggregate / amortized argument structurally identical to the Z-Algorithm proof and the Knuth-Morris-Pratt potential-function argument. The same technique — “successful work pushes a monotone counter forward; the counter is bounded; therefore total work is bounded” — recurs throughout linear-time string algorithms.
7.2 Space
O(n) for the transformed string t and the radius array P. Both can in principle be reconstructed on the fly from a streaming version, but the standard implementation keeps both in memory.
7.3 Why O(n²) “expand around center” is almost always good enough
For n ≤ 1000, both algorithms run in microseconds; the constant factor of expand-around-center is actually smaller and the code is much simpler (10 lines vs 30). Manacher pays off when n ≥ 10⁶ or when palindromic radii are needed for every position (not just the maximum).
LeetCode 5 (“Longest Palindromic Substring”) is solvable with expand-around-center in O(n²) and that solution is typically accepted without hitting time limit. Manacher is the “show off the linear-time chops” answer.
8. Variants and Use Cases
8.1 Count all palindromic substrings (LC 647)
After running Manacher, the number of palindromic substrings centered at index i of the transformed string is (P[i] + 1) // 2 (each radius from 0 to P[i] contributes a distinct palindrome, but only those of valid length matter). Summing across all i gives the total count in O(n).
8.2 Eertree / Palindromic Tree
A different data structure (Rubinchik & Shur 2015) that explicitly stores all distinct palindromic substrings of a string in O(n) total space, supporting incremental updates. More general than Manacher; if you only need the longest palindrome, Manacher is simpler.
8.3 Longest palindromic prefix / suffix
Useful for LeetCode 214 (“Shortest Palindrome”): the shortest palindrome obtainable by prepending characters to s is achieved by reversing the part of s not covered by the longest palindromic prefix. Either Manacher centered at small indices, or the Knuth-Morris-Pratt failure function on s + "#" + reverse(s) (the more common interview answer because KMP is more familiar).
8.4 Palindromic decomposition
LC 132 (“Palindrome Partitioning II”): partition s into the fewest palindromes. Use Manacher to find all palindromic substrings in O(n) and then DP in O(n²) for the partition; this matches the best known time complexity.
8.5 Comparison with hash-based approaches
Rabin-Karp / String Hashing also solve “is s[l..r] a palindrome?” in O(1) after O(n) preprocessing (hash s and reverse(s), compare slice hashes). To find the longest palindrome with hashes you binary-search the radius at every center in O(log n), giving O(n log n) — worse than Manacher’s O(n) but often easier to code if you already have a hashing template at hand.
9. Pitfalls
9.1 Sentinel character collision
If the inserted separator character actually appears in s, palindromes can spuriously cross from one half of the transformed string to the other (or fail to cross when they should). Use a sentinel known absent, or compute one at runtime as in the implementation above.
9.2 The radius/length convention swap
Some references define P[i] as the length 2r + 1 of the palindrome rather than the radius r. The mapping back to the original string changes accordingly. State your convention; never mix two implementations.
9.3 Off-by-one in the extension loop
while t[i + P[i] + 1] == t[i − P[i] − 1] — note the +1 and −1, because P[i] is the current radius and we’re testing the next candidate on each side. A common off-by-one is to write t[i + P[i]] == t[i − P[i]], which compares the already-known endpoints and infinite-loops.
9.4 Forgetting the boundary checks
i + P[i] + 1 < n and i − P[i] − 1 >= 0 is essential — without either, you index out of bounds at the string ends. Don’t rely on Python’s wrap-around behaviour (t[-1] returns the last character, silently corrupting the answer).
9.5 Computing the start position in s
After finding best_i and length = P[best_i], the start in the original string is (best_i − length) // 2, not (best_i − length) (which would be the start in the transformed string). The integer division by 2 maps transformed-string positions back to original positions. This is the most common bug after the convention slip in §9.2.
9.6 Ties on multiple longest palindromes
If multiple palindromes share the maximum length, argmax semantics differ between languages: Python’s max(..., key=...) returns the first; some other languages return the last. The implementation above returns the leftmost (first) longest palindrome; LeetCode 5’s grader accepts any.
9.7 Empty / single-character input
s = "" should return ""; s = "a" should return "a". The transformation still works (t = "#" and t = "#a#" respectively), but the implementation must handle the trivial-radius cases. The Python implementation above handles both correctly.
9.8 Mistaking “longest palindromic subsequence” for “longest palindromic substring”
Subsequences are non-contiguous and require dynamic programming (O(n²) DP, not solvable by Manacher). LeetCode 5 (substring) and LeetCode 516 (subsequence) are different problems with different algorithms; mixing them is the most painful interview slip.
10. Diagram — The Mirror Trick in Action
flowchart TB subgraph "State after processing center c" A["Rightmost palindrome: t[l..r-1] centered at c with radius P[c]"] end subgraph "Processing new index i (i < r)" B["mirror := 2c - i"] C{"Compare known P[mirror] vs r - i"} end subgraph "Three sub-cases" D["Case 1: P[mirror] < r - i — copy P[i] := P[mirror], no new comparisons needed"] E["Case 2: P[mirror] = r - i — copy P[i] := r - i, then attempt to extend (may push r forward)"] F["Case 3: P[mirror] > r - i — copy P[i] := r - i, no extension possible (r boundary blocks it)"] end subgraph "Update window if extended past r" G["if i + P[i] > r: (c, r) := (i, i + P[i])"] end A --> B --> C C --> D --> G C --> E --> G C --> F --> G
What this diagram shows. The control flow at every position i inside the current palindrome window. The mirror position mirror = 2c − i has a known radius P[mirror]; we choose between three sub-cases based on how that radius compares to the distance r − i from i to the window’s right boundary. Cases 1 and 3 are pure copy operations — no character comparisons. Case 2 is the only one that may do new comparison work, and that work always pushes the rightmost-palindrome boundary r strictly forward, which is what gives the algorithm its linear-time amortized cost (proven in §7.1). Outside the window (i ≥ r), there’s no mirror to copy from, so we fall back to naive extension from P[i] = 0.
11. Common Interview Problems
| LC# / Source | Problem | Use of Manacher |
|---|---|---|
| LC 5 | Longest Palindromic Substring | Direct application |
| LC 647 | Palindromic Substrings (count) | Sum of (P[i] + 1) // 2 across all i |
| LC 214 | Shortest Palindrome | Manacher centered near index 0; or KMP equivalent |
| LC 132 | Palindrome Partitioning II | Manacher to find all palindromes, then DP |
| LC 1278 | Palindrome Partitioning III | Same |
| LC 336 | Palindrome Pairs | Manacher per word + Hash Table |
| LC 1745 | Palindrome Partitioning IV | Manacher to test palindrome-substring queries in O(1) |
| Codeforces 17E | Palisection | Count palindromic substring pairs that overlap |
12. Open Questions
- Is there an in-place O(n) algorithm that avoids the 2x memory blow-up of the
#-separator transformation? You can keep two parallel arrays for odd and even radii to skip the transform entirely — slightly more code, half the memory. - How does Manacher’s constant factor compare to expand-around-center on modern CPUs? Empirical benchmarks suggest expand-around-center wins for
n ≤ 5000because of cache effects; Manacher dominates forn ≥ 10⁵. - Why is Manacher so much less-known than Knuth-Morris-Pratt despite being equally elegant? Possibly because palindromes are a less commonly motivated problem in systems work; KMP appears in regex engines, Manacher does not.
13. See Also
- Knuth-Morris-Pratt — same family (linear-time, mirror-trick reuse), for substring search rather than palindromes
- Z-Algorithm — same
[l, r]-window technique - String Hashing — alternative O(n log n) approach via binary search on palindrome radius
- Rabin-Karp — randomized O(n log n) alternative for palindrome detection
- Suffix Array — much heavier machinery; can also find longest palindrome via Eertree-equivalent constructions
- Aho-Corasick — multi-pattern search (orthogonal but neighbouring topic)
- Big-O Notation — for the amortized analysis
- SWE Interview Preparation MOC