Minimum Additions to Form a Palindrome

You are given a string s consisting of n characters. Your task is to transform this string into a palindrome by adding as few characters as possible. A palindrome is a string that reads the same backwards as forwards.

The minimum number of characters to add is given by:

$$n - LPS$$

where n is the length of the string and LPS is the length of the longest palindromic subsequence in s.

For example:

• For s = "aabba", the answer is 1.
• For s = "abcd", the answer is 3.
• For s = "abccba", the answer is 0.

inputFormat

The input consists of a single line containing the string s. The string will only contain ASCII characters.

outputFormat

Output a single integer representing the minimum number of characters that need to be added to make s a palindrome.

aabba

1