Rearrange Characters to Avoid Adjacent Duplicates

You are given a string S consisting of lowercase English letters. Your task is to determine whether the characters of the string can be rearranged such that no two adjacent characters are the same.

In more formal terms, let \( f(c) \) denote the frequency of character \( c \) in the string \( S \). A valid rearrangement exists if and only if:

\( \max_{c} f(c) \leq \left\lceil \frac{|S|}{2} \right\rceil \)

If a valid rearrangement exists, output True; otherwise, output False.

inputFormat

The input consists of a single line containing the string S (1 \( \leq |S| \leq 10^5 \)).

outputFormat

Output a single line containing either True if the characters of S can be rearranged so that no two adjacent characters are the same, or False otherwise.

aab

True