Rearrange Characters

Given a string s, rearrange its characters so that no two adjacent characters are the same. If it is not possible to perform such a rearrangement, output an empty string.

You are required to use a greedy algorithm that always selects the character with the highest remaining frequency (and not equal to the previous character) to build the result.

A useful mathematical condition is to check if the frequency of any character exceeds \(\lceil \frac{n}{2} \rceil\), where \(n\) is the total length of the string, as this makes rearrangement impossible. (Note: this condition is implicit in the algorithm.)

inputFormat

The input is given from stdin as a single line containing the string s. The string may be empty.

outputFormat

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

aab

aba