Minimum Deletions to Make a Palindrome

You are given a string s. Your task is to determine the minimum number of deletions required to convert s into a palindrome. A palindrome is a string that reads the same forwards and backwards.

The challenge can be formulated as follows: given a string s of length n, find the minimal number of deletions needed such that the remaining string is a palindrome. In mathematical notation, if we denote by \(dp(i, j)\) the minimum number of deletions required to make the substring \(s[i\ldots j]\) a palindrome, then the recurrence is given by:

[ \text{if } s[i] = s[j]: \quad dp(i,j) = dp(i+1,j-1) \quad \text{, otherwise: } dp(i,j) = 1 + \min(dp(i+1, j), dp(i, j-1)) ]

Implement the solution using dynamic programming to achieve an efficient answer.

inputFormat

The input consists of a single line containing a non-empty string s composed of lowercase and/or uppercase English letters.

outputFormat

Output an integer representing the minimum number of deletions needed to make the string a palindrome.

abcdba

1