Rearrangement to Avoid Adjacent Duplicates

Given a string S, determine whether it is possible to rearrange its characters so that no two adjacent characters are identical. In other words, you need to check if there exists a permutation of the string such that for every two consecutive characters c_i and c_{i+1}, we have c_i \neq c_{i+1}.

The necessary and sufficient condition for such a rearrangement is that the maximum frequency of any character in the string is at most \(\frac{n+1}{2}\), where \(n\) is the length of the string.

For example:

• If S = "aabb", one valid rearrangement is "abab", so the answer is YES.
• If S = "aaab", no valid rearrangement exists, so the answer is NO.

inputFormat

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

outputFormat

Output YES if it is possible to rearrange the string so that no two adjacent characters are the same; otherwise, output NO.

aabb

YES