Pattern Guide
Palindrome DP Problems
"Minimum cuts, minimum insertions, count palindromic substrings. Interval DP."
Palindrome DP problems optimize over palindromic structure: minimum cuts to partition string into palindromes, minimum insertions to make string a palindrome, count palindromic substrings/subsequences. Core: isPalin[i][j] = (s[i]==s[j]) && isPalin[i+1][j-1]. Built in O(n²). Then use this table as building block for more complex DPs. Distinct from Manacher's (length finding) — these compute optimization or counting.
Problems you can solve with this pattern
4 problems · click any to start solving
// Precompute palindrome table in O(n²)
function buildPalinTable(s) {
const n = s.length;
const isPalin = Array.from({length: n}, () => new Array(n).fill(false));
for (let i = 0; i < n; i++) isPalin[i][i] = true;
for (let i = 0; i < n - 1; i++) isPalin[i][i+1] = s[i] === s[i+1];
for (let len = 3; len <= n; len++)
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
isPalin[i][j] = s[i] === s[j] && isPalin[i+1][j-1];
}
return isPalin;
}
// Minimum palindrome cuts
function minCut(s) {
const n = s.length;
const isPalin = buildPalinTable(s);
const dp = Array.from({length: n}, (_, i) => i); // worst case: i cuts
for (let i = 1; i < n; i++) {
if (isPalin[0][i]) { dp[i] = 0; continue; }
for (let j = 1; j <= i; j++)
if (isPalin[j][i]) dp[i] = Math.min(dp[i], dp[j-1] + 1);
}
return dp[n-1];
}Palindrome table: isPalin[i][j] precomputed in O(n²). Minimum palindrome cuts: dp[i] = min cuts for s[0..i]. For each j ≤ i, if isPalin[j][i], dp[i] = min(dp[i], dp[j-1]+1). Minimum insertions = minimum deletions = n - LPS where LPS = longest palindromic subsequence = LCS(s, reverse(s)). Count palindromic subsequences: dp[i][j] = number of distinct palindromic subsequences in s[i..j].
// Precompute palindrome table in O(n²)
function buildPalinTable(s) {
const n = s.length;
const isPalin = Array.from({length: n}, () => new Array(n).fill(false));
for (let i = 0; i < n; i++) isPalin[i][i] = true;
for (let i = 0; i < n - 1; i++) isPalin[i][i+1] = s[i] === s[i+1];
for (let len = 3; len <= n; len++)
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
isPalin[i][j] = s[i] === s[j] && isPalin[i+1][j-1];
}
return isPalin;
}
// Minimum palindrome cuts
function minCut(s) {
const n = s.length;
const isPalin = buildPalinTable(s);
const dp = Array.from({length: n}, (_, i) => i); // worst case: i cuts
for (let i = 1; i < n; i++) {
if (isPalin[0][i]) { dp[i] = 0; continue; }
for (let j = 1; j <= i; j++)
if (isPalin[j][i]) dp[i] = Math.min(dp[i], dp[j-1] + 1);
}
return dp[n-1];
}- isPalin table: O(n²), foundation for all other problems
- LPS (longest palindromic subsequence) = LCS(s, rev(s))
- Min cuts: O(n²) with isPalin table
- Min insertions = n - LPS
- Min deletions to make palindrome = n - LPS
Interval DP approach: For dp[i][j]: base case when i==j (single char is palindrome). For len≥2: if s[i]==s[j], use inner dp[i+1][j-1]; else take max of excluding either end.