Minimum Operations to Make a String Palindrome

You are given a string s. Your task is to determine the minimum number of removal operations required to make s a palindrome. In each operation, you can remove one character from the string.

This problem can be solved by finding the length of the longest palindromic subsequence (LPS). The answer is given by:

$$\text{answer} = |s| - \text{LPS}(s)$$

where |s| denotes the length of the input string.

inputFormat

The input consists of a single line containing the string s. The string may consist of lowercase and uppercase English letters and may be empty.

outputFormat

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

abc

2