Longest Palindrome Construction

Given a string s, find the length of the longest palindrome that can be constructed by rearranging the characters of s. A palindrome is a word or phrase that reads the same backward as forward. Characters can be rearranged arbitrarily, but each character's frequency is fixed. More formally, if the frequency of each character is given by \( f(c) \), the maximum palindrome length is computed by summing all even frequencies and, for odd frequencies, summing \( (f(c)-1) \) and adding 1 if any odd frequency exists (provided the string is non-empty). For example, if s = "abccccdd", the answer is 7.

Note: In case the input string is empty, the answer is 0.

inputFormat

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

outputFormat

Output a single integer representing the length of the longest palindrome that can be constructed by rearranging the characters of s.

abccccdd

7