Rearrange String

Given a string \( S \), your task is to rearrange its characters so that no two adjacent characters are the same. If such a rearrangement is not possible, return an empty string.

This problem can be solved using a greedy algorithm with a heap (priority queue). At each step, choose the character with the highest remaining frequency that is not equal to the previously placed character. This strategy ensures that the most frequent characters are placed as far apart as possible.

The approach can be mathematically represented as:

( result = \bigoplus_{i=1}^{n} S_i )

where \( S_i \) represents the characters chosen under the condition \( S_i \neq S_{i+1} \) for all valid indices.

inputFormat

The input consists of a single line containing the string \( S \). The string will contain only ASCII characters.

outputFormat

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

aabb

abab