Minimum Removals to Form a Palindrome

You are given a string S. Your task is to determine the minimum number of characters that need to be removed from S so that the remaining characters form a palindrome.

A palindrome is a string that reads the same backward as forward. The problem can be approached using dynamic programming. A key observation is that if you can find the longest palindromic subsequence (LPS) of the string, then the minimum number of removals is given by:

\( \text{min removals} = |S| - \text{LPS length} \)

However, in this problem you are encouraged to use a dynamic programming approach that directly computes the minimum removals by comparing characters and filling a DP table. The recurrence relation used is:

\( dp[i][j] = \begin{cases} dp[i+1][j-1] & \text{if } S[i]=S[j] \\ \min(dp[i][j-1], dp[i+1][j]) + 1 & \text{otherwise} \end{cases} \)

where \( dp[i][j] \) represents the minimum removals for the substring from index \( i \) to \( j \).

inputFormat

The input consists of a single line read from standard input containing the string S.

outputFormat

Output a single integer to standard output representing the minimum number of removals required to transform the string into a palindrome.

racecar

0