Fewest Insertions for a Palindrome
You may insert any characters at any positions. Print the fewest insertions needed to make the string a palindrome.
abcd -> 3 abcdcba
mbadm -> 2 mdbabdm
zzazz -> 0 already a palindrome
Read the first line carefully, because it is the shape of the whole solution. In
abcdcba the original abcd sits at the front and cba has been inserted after it.
The d is the palindrome's centre, so exactly one character of the original was already
in place and the other three each cost one insertion to mirror.
## The reduction
The characters you KEEP form a subsequence of the original, and they must read the same forwards and backwards, because insertions cannot reorder anything.
Conversely, take any palindromic subsequence and the remaining characters can always be mirrored in: for each character not in the subsequence, insert a copy on the other side of the centre. That costs one insertion per omitted character.
So
answer = n - (length of the longest palindromic SUBSEQUENCE)
and problem #423 computes the second term.
Counting what you keep rather than what you add is the same move as problem 478, and it is worth recognising as a move rather than as a fact about palindromes.
## The interval table
``` lps[i][j] = the longest palindromic subsequence of s[i..j]
s[i] == s[j] -> lps[i][j] = 2 + lps[i+1][j-1] otherwise -> lps[i][j] = max( lps[i+1][j], lps[i][j-1] ) ```
with lps[i][i] = 1.
## The fill order, which is the thing to get right
lps[i][j] reads lps[i+1][j-1], lps[i+1][j] and lps[i][j-1]. All three are
SHORTER intervals, so the table must be filled by increasing LENGTH, not by increasing
i or j.
for length in 2..n:
for i in 0..n-length:
j = i + length - 1
A plain nested loop over i then j reads entries that have not been written yet, and in
most languages that means reading zeros, which silently understates the answer.
That is the defining feature of an interval DP and the reason it gets its own topic: the dependency is on shorter intervals, so the loop is over length.
## The length-two case
When length == 2 and the two characters agree, lps[i+1][j-1] is an EMPTY interval with
i+1 > j-1. It must contribute 0. Reading it from the table gives whatever the
initialisation put there, so either initialise the whole table to 0 and rely on it, or
special-case length == 2 explicitly.
ab answers 1 and aabb answers 2, and both go wrong if the empty interval contributes
anything other than 0.
## Boundaries
aba and abcba answer 0: already palindromes, and no insertion is needed.
a answers 0. A single character is a palindrome.
leetcode answers 5, which is the case with no obvious structure.
## Cost
Time O(n^2). Space O(n^2), reducible to O(n) by keeping two diagonals.