The palindrome pattern
Palindrome questions are interval questions: the ends of [i, j] must agree and the inside must already work.
The pattern
A palindrome is defined from the outside in: matching ends around a palindrome. So palindrome questions use the interval state [i, j], filled by increasing length, and the cell asks whether s[i] = s[j] and what the inside [i + 1, j − 1] gives. The earlier modules covered the longest subsequence and substring; the same table counts palindromic substrings and measures how far a string is from being a palindrome.
Palindrome DP
f(i, j)
- if s[i] = s[j]: build on f(i + 1, j − 1);
- otherwise combine f(i + 1, j) and f(i, j − 1).
order
- by increasing j − i.
Worked example: the fewest insertions to make a palindrome
ins(i, j) = ins(i + 1, j − 1) if the ends match, else 1 + min(ins(i + 1, j), ins(i, j − 1)).
For "aaab", by length.
-
Step 1 / 11
Base cases filled first.
-
Step 2 / 11
[0a, 0a] = 0.
-
Step 3 / 11
[1a, 1a] = 0.
-
Step 4 / 11
[2a, 2a] = 0.
-
Step 5 / 11
[3b, 3b] = 0.
-
Step 6 / 11
[0a, 1a] = 0.
-
Step 7 / 11
[1a, 2a] = 0.
-
Step 8 / 11
[2a, 3b] = 1.
-
Step 9 / 11
[0a, 2a] = 0.
-
Step 10 / 11
[1a, 3b] = 1.
-
Step 11 / 11
[0a, 3b] = 1. ins(0, 3) = 1: "aaab" needs one insertion ("baaab").