Longest Palindromic String Length

Given a string s consisting of lowercase English letters, determine the length of the longest palindrome that can be built using the letters of s. A palindrome is a string that reads the same backward as forward. You can rearrange the letters of s arbitrarily.

In mathematical terms, let the frequency of letter i be \(f_i\). The answer is computed as follows:

\[ L = \sum_i \left(f_i - (f_i \bmod 2)\right) + \begin{cases} 1, & \text{if any } f_i \bmod 2 = 1 \\ 0, & \text{otherwise} \end{cases} \]

For example, if s = "abccccdd", the answer is 7.

inputFormat

The input is read from standard input and consists of a single line containing a string s (1 ≤ |s| ≤ 10⁵), where each character is a lowercase English letter.

outputFormat

Output a single integer — the length of the longest palindromic string that can be built from the input string.

a

1