Pattern Guide
Manacher's Algorithm
"Find all palindromic substrings in O(n). Extends each palindrome using previous results."
Manacher's algorithm finds the longest palindromic substring and the radius of every palindrome centered at each position in O(n) time. It cleverly reuses previously computed palindrome radii using a "mirror" observation within the rightmost palindrome seen so far. The standard trick of inserting separators (#) between characters unifies odd and even length palindromes.
Problems you can solve with this pattern
4 problems · click any to start solving
// 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);
}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.
// 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);
}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.