Minimum Removals to Rearrange into Palindrome

You are given a string s consisting of lowercase English letters. Your task is to determine the minimum number of characters that must be removed from s so that the remaining characters can be rearranged to form a palindrome.

A palindrome is a sequence of characters that reads the same forward and backward. In order to rearrange characters of a string into a palindrome, at most one character may appear an odd number of times. Thus, if we let \(odd\_count\) be the number of characters with odd frequencies, the answer is given by:

$$\max(0, odd\_count - 1)$$

For example:

• For s = "aabbcc", all characters appear an even number of times so no removals are needed.
• For s = "abc", all characters appear once (odd frequency), so you need to remove 2 characters leaving one character to form a palindrome.
• For s = "abccbaac", only one removal is required.

Read the input from standard input and output the result to standard output.

inputFormat

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

outputFormat

Output a single integer, the minimum number of removals required so that the remaining characters can be rearranged to form a palindrome.

aabbcc

0