Longest Palindromic Subsequence from Characters

Given a string P, you can rearrange its characters to form a palindromic string. Your task is to determine the maximum possible length of a palindromic string that can be formed using all or some of the characters from P. A palindrome is a string that reads the same forwards and backwards.

For example:

• If P = "abba", the answer is 4.
• If P = "aabbbcc", the answer is 7, since you can rearrange them for a palindrome like "abcbbca".
• If P = "abcd", the answer is 1 because no two characters are the same.
• If P = "aabbc", the answer is 5 by rearranging to form something like "abcba".

The underlying idea is to use the frequencies of characters. For each character, you can use an even number of occurrences, and at most one additional character (if any frequency is odd) can be placed in the middle.

Mathematically, if the frequency of a character is \( f \), you can contribute \( f - (f \bmod 2) \) characters to the palindrome, and if there exists at least one character with an odd frequency, then you may add 1 to the overall length. In LaTeX, the formula can be expressed as:

[ \text{max_length} = \sum_{\text{for each character}} \left(f - (f \bmod 2)\right) + \begin{cases}1, & \text{if there exists a character with odd frequency} \ 0, & \text{otherwise}\end{cases} ]

inputFormat

The input consists of a single line containing the string P composed of ASCII characters.

outputFormat

Output a single integer on one line, representing the maximum length of a palindromic string that can be constructed from the characters of P.

## sample

abba

4