Rearranging Characters to Avoid Adjacent Duplicates

You are given a string s consisting of English letters. Your task is to determine whether it is possible to rearrange its letters so that no two adjacent characters are the same.

The condition for such a rearrangement to be possible is based on the frequency of the most frequent character. Let n be the length of the string and f_max be the maximum frequency among all characters. A necessary and sufficient condition is:

$$2 \times f_{max} - 1 \leq n.$$

If the condition is satisfied, output True; otherwise, output False.

Example:

• For s = "aabb", we have f_max = 2 and n = 4. Since 2*2-1 = 3 \leq 4, the output is True.
• For s = "aaab", we have f_max = 3 and n = 4. Since 2*3-1 = 5 > 4, the output is False.

inputFormat

The input consists of a single line containing a non-empty string s composed of English letters.

Read the input from standard input (stdin).

outputFormat

Output True if the characters can be rearranged so that no two adjacent characters are identical, otherwise output False. Write the result to standard output (stdout).

## sample

aabb

True