Minimum String Length after Pair Removal

You are given a string S consisting of lowercase English letters. You can repeatedly remove two identical characters from the string. Formally, for any character c, if it appears at least twice, you may remove two instances of c (not necessarily adjacent). After performing such operations optimally, some characters may remain unremovable.

The minimized length of the string is given by the number of characters whose frequency is odd. In mathematical terms, if for each character c the frequency is f(c), then the answer is:

For example, if S = "abacaba", the frequencies are: a: 4, b: 2, c: 1. Only 'c' has an odd count, so the minimized length is 1.

inputFormat

The input consists of a single line containing the string S (1 ≤ |S| ≤ 1000).

outputFormat

Output a single integer — the minimized length of the string after performing the optimal pair removal operations.

abacaba

1