Minimum Steps to Palindrome

You are given a non-empty string s consisting of lowercase letters. Your task is to determine the minimum number of deletion operations required to transform s into a palindrome. A string is a palindrome if it reads the same backward as forward.

In each operation, you may remove exactly one character. Formally, let \(dp(i,j)\) denote the minimum number of deletions required for the substring \(s[i\ldots j]\). The recurrence relation is given by:

$$ \begin{cases} 0, & \text{if } i \geq j,\\ dp(i+1,j-1), & \text{if } s[i]=s[j],\\ \min(dp(i+1,j),\;dp(i,j-1)) + 1, & \text{if } s[i]\neq s[j]. \end{cases} $$

Your goal is to compute \(dp(0,n-1)\) where \(n\) is the length of s.

inputFormat

The input consists of a single line containing the string s (with length at least 1 and up to 1000 characters).

outputFormat

Output a single integer representing the minimum number of deletions required to convert s into a palindrome.

## sample

abccba

0