Minimum Operations to Convert String into Palindrome

Given a string s consisting of lowercase English letters, your task is to determine the minimum number of operations required to convert s into a palindrome. In one operation, you can remove any single character from the string. A palindrome is a string that reads the same forwards and backwards.

Details:

• If the string is already a palindrome, no operations are needed.
• You are allowed to perform the deletion operation on any character from the string.

Mathematically, if we denote the minimum operations required on string s as \( dp[0][n-1] \) where \( n \) is the length of s, then for any indices \( l \) and \( r \) (with \( l < r \)), we have:

[ \text{dp}[l][r] = \begin{cases} 0, & \text{if } l \geq r \ \text{dp}[l+1][r-1], & \text{if } s[l] = s[r] \ 1 + \min(\text{dp}[l+1][r], \text{dp}[l][r-1]), & \text{if } s[l] \neq s[r] \end{cases} ]

Your program should read the input from stdin and output the result to stdout.

inputFormat

The input consists of a single line containing the string s.

Constraints: 1 \( \leq \) |s| \( \leq \) 1000, and s contains only lowercase English letters.

outputFormat

Output a single integer which is the minimum number of operations (deletions) needed to convert the input string into a palindrome.

## sample

abc

2