Minimum Deletions to Palindrome

Given a string s, determine the minimum number of characters that need to be deleted in order to transform s into a palindrome. A palindrome is a sequence that reads the same backward as forward.

The problem can be solved by finding the longest palindromic subsequence (LPS) in the given string. The answer is the difference between the string's length and the length of the LPS. In mathematical terms, if n is the length of the string and LPS is the length of the longest palindromic subsequence, the minimum number of deletions required is:

$$\text{Deletions} = n - LPS$$

For example, for the input abca, the output is 1 because by deleting the character "b" or "c", the string becomes a palindrome.

inputFormat

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

The string will only contain lowercase English letters.

outputFormat

Output a single integer which is the minimum number of deletions required to make the string a palindrome.

abca

1