Longest Palindromic Subsequence Length

You are given a string S. Your task is to compute the length of the longest subsequence of characters from S that can be rearranged to form a palindrome.

A palindrome is a string that reads the same backward as forward. In order to form a palindrome from a set of characters, at most one character is allowed to have an odd frequency, while the others should appear an even number of times. More formally, if the frequency of each character is given by \(f(c)\) for a character \(c\), the length of the longest possible palindromic arrangement is computed as follows:

\[ \text{result} = \sum_{c} 2 \left\lfloor \frac{f(c)}{2} \right\rfloor + \begin{cases}1, & \text{if any } f(c) \text{ is odd}\\0, & \text{otherwise}\end{cases} \]

Input/Output Format: The input is read from stdin and the result should be printed to stdout.

inputFormat

The input consists of a single line containing the string S (which may be empty). The string only contains printable ASCII characters.

outputFormat

Output a single integer, the length of the longest subsequence that can be rearranged to form a palindrome.

abcaabaa

7