StringsAlgorithmaka longest palindromic substring in linear time, palindrome radii

Manacher's Algorithm

Compute the palindrome radius around every center in O(n) by reusing mirrored radii inside the rightmost known palindrome.

▶ VisualizePattern: Two PointersPractice (1)
Progress

Overview

Manacher's algorithm finds the longest palindromic substring — and in fact the maximal palindrome centered at every position — in linear time. The plain center-expansion method tries each of the 2n - 1 centers and expands outward, which is O(n²) on inputs like "aaaa…a". Manacher keeps the expansion but skips the part that a previously found palindrome already proves.

To treat odd- and even-length palindromes uniformly, the string is transformed by inserting a separator between characters: "abba" becomes "^#a#b#b#a#$". In the transformed string every palindrome has odd length and a well-defined center, and the radius p[i] in the transformed string equals the length of the original palindrome.

palindromeO(n)center expansionmirror trick

Intuition

A mental model before the formal terms.

A palindrome is symmetric about its center. If you are standing inside a big palindrome [l, r] centered at c, then whatever is at position i looks exactly like what is at the mirror position 2c - i. So a small palindrome around the mirror implies an equally large palindrome around i — at least as far as the big palindrome's boundary. That is the mirror trick: copy the mirror's radius, capped at the distance to r, and only expand beyond that boundary with real character comparisons.

Every real comparison either fails (ending this center) or extends r further right. Since r only moves right and stops at n, the total number of successful comparisons is O(n).

How it works

  1. Build t = "^#" + "#".join(s) + "#$". The sentinels ^ and $ never match anything, so expansion needs no bounds checks.
  2. Keep c (center) and r (right edge) of the palindrome that currently reaches furthest right. For each i from 1 to len(t) - 2: let mirror = 2c - i. If i < r, initialise p[i] = min(r - i, p[mirror]); otherwise p[i] = 0.
  3. Center expansion: while t[i + p[i] + 1] == t[i - p[i] - 1], increment p[i].
  4. If i + p[i] > r, this palindrome extends further right than any before: set c = i, r = i + p[i].
  5. The answer is the maximum p[i]; in the original string it starts at (i - p[i]) / 2 and has length p[i].

Why it works

Let the palindrome centered at c span [c - p[c], c + p[c]] and let i lie inside it with mirror j = 2c - i. Reflecting through c maps the substring around j onto the substring around i reversed; so any palindrome around j that stays within [c - p[c], c + p[c]] reflects to a palindrome of the same radius around i. That is why p[i] ≥ min(p[j], r - i). Beyond r nothing is known, hence the cap and the explicit expansion.

If the mirror's palindrome is strictly shorter than r - i, then p[i] = p[j] exactly (a longer one around i would reflect to a longer one around j), and the expansion loop fails immediately. Otherwise the expansion starts at r and every success increases r. So the amortised cost is O(n).

Recognition

How to tell a problem wants this.

  • The problem asks for the longest palindromic substring, or for the number of palindromic substrings, with n up to 10^5 or more.
  • You need the maximal palindrome centered at every position (e.g. counting palindromic substrings, palindromic partition speed-ups).
  • Center expansion is the obvious approach but the input can be a single repeated character.
“sorted array” → Two Pointers

Interactive visualization

Play, step, change the input. ← → and space work too.

a
#
0
b
1
#
2
a
3
#
4
b
5
#
6
a
7
#
8
d
9
#
10
P
0
1
2
3
4
5
6
7
8
9
10
1/24Insert '#' between characters so every palindrome has odd length (5 chars become 11). P[i] will hold the radius of the palindrome centred at i.
Current center iCharacters being expandedRightmost palindrome [c - r, c + r]Longest palindrome
PseudocodeLearn Manacher's Algorithm →
1t = "#" + "#".join(s) + "#"; P = [0]*len(t); c = r = 0
2for i in 0 .. len(t)-1:
3  mirror = 2*c - i
4  if i < r: P[i] = min(r - i, P[mirror])
5  while t[i + P[i] + 1] == t[i - P[i] - 1]: P[i] += 1
6  if i + P[i] > r: c = i; r = i + P[i]
7answer = longest P[i]; palindrome = s[(i - P[i]) / 2 .. +P[i]]
Variables
c0
r0
Complexity
best O(n)
avg O(n)
worst O(n)
space O(n)
Speed

Pseudocode

1t = "^#" + "#".join(s) + "#$"; p = zeros; c = r = 0
2for i in 1 .. len(t) - 2:
3  mirror = 2c - i
4  if i < r: p[i] = min(r - i, p[mirror])
5  while t[i + p[i] + 1] == t[i - p[i] - 1]: p[i] += 1
6  if i + p[i] > r: c = i, r = i + p[i]
7best = argmax p; start = (best - p[best]) / 2; return s[start .. start + p[best])

Implementations

1def longest_palindrome(s: str) -> str:
2    if not s:
3        return ""
41 · Transform with separators and sentinels
5    t = "^#" + "#".join(s) + "#$"
6    n = len(t)
7    p = [0] * n  # palindrome radius around each center of t
8    c = r = 0    # center and right edge of the rightmost palindrome
9    for i in range(1, n - 1):
102 · Mirror the radius inside the current palindrome
11        mirror = 2 * c - i
12        if i < r:
13            p[i] = min(r - i, p[mirror])
143 · Expand around the center
15        while t[i + p[i] + 1] == t[i - p[i] - 1]:
16            p[i] += 1
174 · Update the rightmost palindrome
18        if i + p[i] > r:
19            c, r = i, i + p[i]
205 · Map the best radius back to the original string
21    best = max(range(1, n - 1), key=lambda i: p[i])
22    start = (best - p[best]) // 2
23    return s[start:start + p[best]]
Walkthrough
  1. "#".join(s) treats the string as an iterable of characters and inserts the separator between all of them — one linear pass, no explicit loop.
  2. p = [0] * n and c = r = 0 set up the radius array and the rightmost-palindrome bookkeeping.
  3. The while loop is the only place characters are compared; the sentinels ^ and $ guarantee it terminates without index errors.
  4. max(range(1, n - 1), key=lambda i: p[i]) returns the index of the best center directly.
  5. s[start:start + p[best]] slices the answer out of the original string; the radius in t equals the length in s.
Complexity (this implementation)
time O(n) · space O(n)

The final slice copies the answer (Python slices always copy); return (start, length) to avoid it.

Language notes
  • str.join is the canonical linear-time way to interleave; += in a loop is quadratic in principle (CPython sometimes optimises it, but do not rely on that).
  • // keeps start an int; a single / would produce a float and break slicing.
  • max(iterable, key=...) avoids the manual argmax loop other languages need.
Common mistakes in this language
  • Using / instead of // for the start index and getting TypeError: slice indices must be integers.
  • Running i over range(n) including the sentinels, which expands out of bounds.
  • Taking max(p) (the radius) when the problem needs the substring — the index is what maps back.
Language differences that matter here
  • Building the transformed string: Python "#".join(s) and JS/TS split/join are single-pass; C++ += into a reserved std::string avoids the intermediate array the script languages create.
  • Integer division for the back-mapping: Python needs //, C++ int division truncates natively, JS/TS / happens to be exact here because the operands share parity — but Math.floor documents intent.
  • Unicode: the transform indexes code units in JS/TS and code points in Python; C++ works on bytes. For non-ASCII input the three can disagree about what a "character" is — normalise or split by code points first.
  • substr(start, length) in C++ vs substring(start, end) in JS/TS vs slice s[a:b] in Python — three different conventions for extracting the final answer.

Complexity

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(n)

The transformed string and radius array are each about 2n + 3 entries.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Longest palindromic substring with large n.
  • Counting all palindromic substrings: the answer is Σ ⌈p[i] / 2⌉ over the transformed string.
  • Any problem needing the maximal palindrome radius at every center as a preprocessing step.
Avoid it when
  • Small inputs (n ≤ 1000) where O(n²) center expansion is simpler and fast enough.
  • Palindromic subsequences — that is a Subsequence DP problem, not a substring one.
  • Palindromes under edits or with wildcards — Manacher assumes exact symmetry.

Alternatives

2D (Two-Sequence) DPRolling Hash (Polynomial Hashing)Suffix Array

Common mistakes

  • Omitting the sentinels ^ and $ and then reading outside the array during expansion.
  • Using i <= r instead of i < r (or mixing up inclusive and exclusive r), which copies a radius the current palindrome does not vouch for.
  • Forgetting to cap p[mirror] by r - i.
  • Converting back to the original string incorrectly — the start index is (i - p[i]) / 2 and the length is p[i], not 2p[i] + 1.

Interview patterns

  • Longest palindromic substring in O(n) (follow-up after the O(n²) expansion solution).
  • Count palindromic substrings.
  • Shortest palindrome by prepending characters: longest palindromic prefix.
  • Palindrome pairs and palindromic partitioning with precomputed radii.
Interview questions on this
Mock interviews

Example problems

Longest Palindromic Substringmedium