Pattern Reference
Palindrome Patterns
"Longest palindromic substring (Manacher's), count palindromes, palindrome partitioning, break a palindrome."
Loading...
Deep Dive Tutorial
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
}Worked Problems
flip-horizontal-2
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