Reorder String to Avoid Adjacent Duplicates

Given a string s consisting of lowercase English letters, determine whether it is possible to reorder its characters so that no two adjacent characters are the same.

The key observation is that a valid reordering exists if and only if the maximum frequency of any character does not exceed $$\lceil \frac{n}{2} \rceil$$, where n is the length of the string.

For example, if s = "aab", the characters can be rearranged (e.g. "aba") such that no two identical characters are adjacent, so the answer is True. On the other hand, for s = "aaab", no valid reordering exists, so the answer is False.

inputFormat

The input is provided as a single line from the standard input, containing a string s of lowercase English letters.

outputFormat

Output True if it is possible to reorder s so that no two adjacent characters are the same, otherwise output False. The output should be printed on a single line to the standard output.## sample

aab

True