Rearrange String

Given a string s, rearrange its characters so that no two adjacent characters are the same. If such an arrangement is impossible, output an empty string. The string consists of lowercase English letters only.

You are encouraged to use a greedy algorithm along with a max-heap data structure. In particular, you can use the following idea: at each step, choose the character with the highest remaining frequency that is different from the previously chosen character. If at any step no such character exists, then output an empty string.

Note: Multiple valid outputs might exist. Your solution only needs to output one valid rearrangement.

The underlying idea can be mathematically related to the condition that if the maximum frequency of any character is greater than \(\lceil \frac{n}{2} \rceil\), then a valid rearrangement is impossible.

inputFormat

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

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