Pattern Reference
Manacher's Algorithm
"Longest palindromic substring in O(n) using symmetry expansion and center caching."
Loading...
Deep Dive Tutorial
Manacher's works by maintaining the rightmost palindrome's right boundary R and center C. For each position i: if i < R, the mirror of i around C gives a starting estimate for p[i] (palindrome radius). Then expand manually. Update C and R when a longer palindrome is found. Transform string to insert '#' separators so all palindromes are odd-length in the transformed string.
Manacher's algorithm
// Returns p[i] = radius of longest palindrome centered at transformed[i]
// Transformed: "#a#b#a#" — every palindrome becomes odd-length
function manacher(s) {
// Transform: insert '#' between chars and at ends
const t = '#' + s.split('').join('#') + '#';
const n = t.length;
const p = new Array(n).fill(0);
let c = 0, r = 0; // center and right boundary of rightmost palindrome
for (let i = 0; i < n; i++) {
if (i < r) {
const mirror = 2 * c - i;
p[i] = Math.min(r - i, p[mirror]);
}
// Expand around center i
while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && t[i - p[i] - 1] === t[i + p[i] + 1]) {
p[i]++;
}
// Update rightmost palindrome
if (i + p[i] > r) { c = i; r = i + p[i]; }
}
return p; // p[i] = radius in transformed string = length in original: p[i] counts '#' too
// Actual palindrome length at transformed position i = p[i]
// Corresponds to original substring of length p[i] centered at i/2 (approximately)
}
function longestPalindrome(s) {
const p = manacher(s);
const t = '#' + s.split('').join('#') + '#';
let maxLen = 0, center = 0;
for (let i = 0; i < t.length; i++) {
if (p[i] > maxLen) { maxLen = p[i]; center = i; }
}
// Convert back: original start = (center - maxLen) / 2
const start = (center - maxLen) / 2;
return s.slice(start, start + maxLen);
}Worked Problems
flip-horizontal-2
Manacher's key insight: If i < R (inside rightmost palindrome), mirror position 2C-i gives a starting estimate — we know p[i] ≥ min(R-i, p[mirror]). Can't go beyond R without checking, so we always expand from there.
Transformed string trick: "#a#b#a#" makes all palindromes odd-length. p[i] in transformed = palindrome radius. Original palindrome length = p[i]. Original start = (i - p[i]) / 2.
vs expand around center: Manacher's O(n) vs O(n²). Use Manacher's when you need all palindrome radii. For single longest palindrome, expand-around-center is simpler.
Transformed string trick: "#a#b#a#" makes all palindromes odd-length. p[i] in transformed = palindrome radius. Original palindrome length = p[i]. Original start = (i - p[i]) / 2.
vs expand around center: Manacher's O(n) vs O(n²). Use Manacher's when you need all palindrome radii. For single longest palindrome, expand-around-center is simpler.