Minimum Removals to Palindrome

Given a string (s), your task is to calculate the minimum number of characters that need to be removed so that the resulting string becomes a palindrome. A palindrome is a string that reads the same forward and backward.

The problem can be formulated using the following dynamic programming recurrence. Let (dp[i][j]) be the minimum number of removals required to convert the substring (s[i \ldots j]) into a palindrome. Then, [ dp[i][j] = \begin{cases} 0, & \text{if } i \ge j \ dp[i+1][j-1], & \text{if } s[i] = s[j] \ 1 + \min(dp[i+1][j], dp[i][j-1]), & \text{if } s[i] \neq s[j] \end{cases} ] Your program should read the input string from standard input and output the minimum number of removals to standard output.

inputFormat

The input consists of a single line containing the string (s). The string will contain only printable characters and its length will be at least 1.

outputFormat

Output a single integer which is the minimum number of characters that need to be removed to transform the string into a palindrome.## sample

abbaa

1