Longest Even Palindrome Subsequence

Given a string s consisting of lowercase letters, find the length of the longest subsequence that forms a palindrome in which every character appears an even number of times. In other words, for each letter c in the subsequence, its frequency must be even. The answer can be computed using the formula:

\[ \text{Answer} = \sum_{c\in \text{letters}} \begin{cases} count(c), & \text{if } count(c) \text{ is even} \\ count(c)-1, & \text{if } count(c) \text{ is odd} \end{cases} \]

For example, for s = "abccccdd", the counts are: a: 1, b: 1, c: 4, d: 2. Thus the answer is 0 + 0 + 4 + 2 = 6.

inputFormat

The input is provided via standard input (stdin) as a single line containing the string s composed of lowercase English letters.

outputFormat

Output the length of the longest even palindrome subsequence to standard output (stdout) as an integer.

abccccdd

6