Minimum Removals to Form Palindrome

Given a string \( s \), determine the minimum number of characters that must be removed so that the remaining string is a palindrome. A palindrome is a string that reads the same backward as forward. One effective approach to solve this problem is to compute the length of the Longest Palindromic Subsequence (LPS) of \( s \) and then subtract this length from the total length of \( s \). The formula is:

\[ \text{Minimum Removals} = |s| - \text{LPS}(s) \]

The input string may consist of various characters. Your program should read from standard input and print the result to standard output.

inputFormat

The input is provided via standard input. It consists of a single line containing the string \( s \).

outputFormat

Output a single integer representing the minimum number of characters that need to be removed from \( s \) to turn it into a palindrome. The result should be printed to standard output.

abca

1