Pattern Guide
Palindrome Patterns
"Expand from center, or DP on intervals. Two approaches cover every palindrome problem."
Palindrome problems ask about strings that read the same forwards and backwards. The expand-around-center technique solves longest palindromic substring in O(n²). DP on intervals solves minimum cuts and counts. Manacher's solves longest in O(n). Learn when each approach applies.
16 min readdp problems →
Problems you can solve with this pattern
5 problems · click any to start solving
Expand around center — counts and finds palindromes
// For each center (2n-1 possible centers), expand outward
// Odd length: center at i. Even length: center between i and i+1
function expandAroundCenter(s) {
let longest = '';
let count = 0;
const expand = (l, r) => {
while (l >= 0 && r < s.length && s[l] === s[r]) {
count++; // every valid [l,r] is a palindrome
if (r - l + 1 > longest.length) longest = s.slice(l, r+1);
l--; r++;
}
};
for (let i = 0; i < s.length; i++) {
expand(i, i); // odd length (single center)
expand(i, i + 1); // even length (between two chars)
}
return { longest, count };
}
// Manacher's O(n) — transforms string with separators
// "#a#b#a#" → finds all palindrome radii in O(n) using mirror property
function manacher(s) {
const t = '#' + s.split('').join('#') + '#';
const n = t.length;
const p = new Array(n).fill(0); // p[i] = radius of palindrome centered at i
let center = 0, right = 0;
for (let i = 0; i < n; i++) {
const mirror = 2 * center - i;
if (i < right) p[i] = Math.min(right - i, p[mirror]);
// Expand beyond known palindrome
while (i-p[i]-1>=0 && i+p[i]+1<n && t[i-p[i]-1]===t[i+p[i]+1]) p[i]++;
if (i+p[i] > right) { center=i; right=i+p[i]; }
}
return p; // p[i]/2 = radius in original string, skip '#' positions
}Palindrome problems divide into two families: (1) substring problems ("find/count/longest palindromic substring") which use expand-around-center or Manacher's algorithm, and (2) subsequence/partition problems ("longest palindromic subsequence," "minimum cuts") which use DP on intervals. The first is simpler; the second requires the interval DP pattern.
| Problem | Approach | Complexity |
|---|---|---|
| Check if string is palindrome | Two pointers from ends | O(n) |
| Longest palindromic substring | Expand around center (O(n²)) or Manacher's (O(n)) | O(n²) or O(n) |
| Count palindromic substrings | Expand around center | O(n²) |
| Longest palindromic subsequence | LCS(s, reverse(s)) or interval DP | O(n²) |
| Minimum cuts for palindrome partition | DP with isPalin precomputed | O(n²) |
| All palindrome partitions | Backtracking + isPalin pruning | O(2^n × n) |
| Shortest palindrome (prefix) | KMP trick | O(n) |
Expand Around Center Template
Expand around center — counts and finds palindromes
// For each center (2n-1 possible centers), expand outward
// Odd length: center at i. Even length: center between i and i+1
function expandAroundCenter(s) {
let longest = '';
let count = 0;
const expand = (l, r) => {
while (l >= 0 && r < s.length && s[l] === s[r]) {
count++; // every valid [l,r] is a palindrome
if (r - l + 1 > longest.length) longest = s.slice(l, r+1);
l--; r++;
}
};
for (let i = 0; i < s.length; i++) {
expand(i, i); // odd length (single center)
expand(i, i + 1); // even length (between two chars)
}
return { longest, count };
}
// Manacher's O(n) — transforms string with separators
// "#a#b#a#" → finds all palindrome radii in O(n) using mirror property
function manacher(s) {
const t = '#' + s.split('').join('#') + '#';
const n = t.length;
const p = new Array(n).fill(0); // p[i] = radius of palindrome centered at i
let center = 0, right = 0;
for (let i = 0; i < n; i++) {
const mirror = 2 * center - i;
if (i < right) p[i] = Math.min(right - i, p[mirror]);
// Expand beyond known palindrome
while (i-p[i]-1>=0 && i+p[i]+1<n && t[i-p[i]-1]===t[i+p[i]+1]) p[i]++;
if (i+p[i] > right) { center=i; right=i+p[i]; }
}
return p; // p[i]/2 = radius in original string, skip '#' positions
}Palindrome algorithm selector:
- "Is this a palindrome?" → two pointers, O(n)
- "Longest palindromic substring" → expand around center O(n²) or Manacher's O(n)
- "Count palindromic substrings" → expand around center, count on each step
- "Longest palindromic subsequence" → LCS(s, reverse(s)) = O(n²)
- "Min cuts / min insertions" → LPS relationship:
- min cuts = n - LPS would be wrong; use separate DP
- min insertions = n - LPS(s)
- "Can become palindrome with k deletions?" → n - LPS ≤ k
- "Palindrome prefix" → KMP LPS last value
- "Is this a palindrome?" → two pointers, O(n)
- "Longest palindromic substring" → expand around center O(n²) or Manacher's O(n)
- "Count palindromic substrings" → expand around center, count on each step
- "Longest palindromic subsequence" → LCS(s, reverse(s)) = O(n²)
- "Min cuts / min insertions" → LPS relationship:
- min cuts = n - LPS would be wrong; use separate DP
- min insertions = n - LPS(s)
- "Can become palindrome with k deletions?" → n - LPS ≤ k
- "Palindrome prefix" → KMP LPS last value