Rearrange String to Avoid Adjacent Duplicates

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

For example:

• For s = "aab", one possible rearrangement is "aba".
• For s = "aaab", it is impossible to rearrange the string to meet the criteria, so the output should be an empty string.

Note: There may be multiple valid rearrangements. Your program is required to output the rearrangement produced by the implemented algorithm.

The problem can be solved using a greedy algorithm that uses a priority queue (or max heap) to always choose the character with the highest remaining frequency that is not equal to the previously chosen character.

inputFormat

The input consists of a single line containing a non-empty string s.

Input is taken from standard input (stdin).

outputFormat

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

Output should be written to standard output (stdout).

## sample

aab

aba