Rearrange String Without Adjacent Duplicates

Given a string s consisting of lowercase letters, rearrange its characters so that no two adjacent characters are the same. If such a rearrangement is possible, output any one valid rearrangement; otherwise, output an empty string.

It is known that a valid rearrangement exists if and only if for every character, its frequency does not exceed \(\lceil \frac{n}{2} \rceil\), where \(n\) is the length of the string.

Examples:

• For input aab, one valid rearrangement is aba.
• For input aaab, no valid rearrangement exists so the output should be an empty string.

inputFormat

The input consists of a single line containing the string s (only lowercase letters).

outputFormat

Output a single line containing the rearranged string such that no two adjacent characters are the same. If no valid rearrangement exists, output an empty string.

aab

aba