Minimum Insertions to Make a Palindrome
mediumDynamic Programming II+20 XPTime limit 3s
You may insert characters anywhere in a word (at the start, the end or in between). What is the minimum number of insertions that turns it into a palindrome (reads the same forwards and backwards)?
Input: one line with the word.
Output: the minimum number of insertions.
Constraints: 1 ≤ length ≤ 1000; lowercase letters.
Example: abcda → adbcbda needs 2 insertions.
Think about it: the characters you keep without a partner form a palindrome subsequence of the word — keep the longest one, and every other character needs one inserted twin. Answer = n − LPS, and the longest palindromic subsequence equals LCS(word, reverse(word)). Or directly: f(i, j) = f(i+1, j−1) if the ends match, else 1 + min(f(i+1, j), f(i, j−1)).
Sample input 1
abcda
Sample output 1
2
Sample input 2
racecar
Sample output 2
0
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).