Skills101
← All coding problems

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).

Loading editor…

Log in to run and submit your code — it's free.