Longest Palindrome Construction

Given a string s consisting of characters, determine the length of the longest palindrome that can be constructed by rearranging the characters of s. A palindrome reads the same backward as forward. You can use each character at most as many times as it appears in the string.

Formally, let the frequency of a character c in s be \( f(c) \). Then the maximum length of a palindrome that can be constructed is given by:

\[ L = \Bigl(\sum_{c} (f(c) - (f(c) \bmod 2))\Bigr) + \begin{cases} 1 & \text{if at least one } f(c) \text{ is odd} \\ 0 & \text{otherwise} \end{cases} \]

Input will be provided as a single string from stdin and the result should be printed as an integer to stdout.

inputFormat

The input consists of a single line containing the string s.

Constraints:

• The string s may contain any ASCII characters.

outputFormat

Output a single integer representing the length of the longest palindrome that can be constructed from the characters of the string.

a

1