Longest Even Subsequence

Given a string s, your task is to compute the length of the longest subsequence in which every character appears an even number of times. A subsequence is derived by deleting zero or more characters without changing the order of the remaining characters. The solution can be computed by summing, for each character c in s, the largest even number not exceeding its frequency f(c). In mathematical terms, the length can be expressed as: $$\text{LongestEvenSubsequence}(s)=\sum_{c \in s} \left\lfloor \frac{f(c)}{2} \right\rfloor \times 2.$$ Note that s can be very large (up to 10^6 characters), so an efficient solution is required.

inputFormat

The input consists of a single line read from standard input (stdin) which is the string s.

outputFormat

The output is a single integer printed to standard output (stdout) representing the length of the longest subsequence where every character occurs an even number of times.## sample

aabbccdd

8