Minimum Operations to Transform a String into a Palindrome

You are given a string s of length n. Your task is to determine the minimum number of deletion operations required to transform the string into a palindrome. A palindrome is a string that reads the same backward as forward.

The trick is to recognize that the minimum number of deletions needed is equal to the length of the string minus the length of its longest palindromic subsequence (LPS). The LPS can be computed using the longest common subsequence (LCS) between the string and its reverse.

Note: Only deletion operations are allowed.

Example:

• For s = "abcba" of length 5, no deletions are required since it is already a palindrome.
• For s = "abc" of length 3, two deletions are required.

inputFormat

The input is provided via standard input (stdin) and has the following format:

n
s

where:

• n is an integer representing the length of the string.
• s is the string consisting of lowercase or uppercase letters.

outputFormat

Output a single integer to standard output (stdout): the minimum number of deletion operations required to convert s into a palindrome.

## sample

5
abcba

0