Minimum Deletions to Make a Palindrome

Given a string s, your task is to determine the minimum number of deletions required so that the resulting string is a palindrome. A palindrome is a string that reads the same backward as forward.

This problem can be solved using the concept of the Longest Palindromic Subsequence (LPS). The minimum number of deletions needed is given by the formula:

\( \text{deletions} = n - \text{LPS}(s) \)

where \( n \) is the length of the string and \( \text{LPS}(s) \) is the length of the longest subsequence of s that is a palindrome.

Good luck!

inputFormat

The input consists of a single line containing the string s. The string's length is at least 1. Input is provided via standard input.

outputFormat

Output a single integer representing the minimum number of deletions required to transform the string into a palindrome. Output should be printed to standard output.

1433541

1