Minimum Deletions to Form a Palindrome

You are given a string s consisting of lowercase English letters. Your task is to determine the minimum number of deletions required to transform s into a palindrome.

A palindrome is a string that reads the same forwards and backwards. Formally, a string s of length n is a palindrome if:

\( s[i] = s[n-i-1] \) for all \( 0 \le i < n \).

One way to solve this problem is to use dynamic programming. Let \( dp[i][j] \) denote the minimum number of deletions required to convert the substring \( s[i \ldots j] \) into a palindrome. The recurrence relation is given by:

\( dp[i][j] = \begin{cases} 0, & \text{if } i \geq 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 task is to compute \( dp[0][n-1] \), which is the minimum number of deletions required for the entire string.

inputFormat

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

Constraints:

• s contains only lowercase English letters.

outputFormat

Output a single integer representing the minimum number of deletions required to transform the input string into a palindrome.

## sample

abccba

0