Reorganize String

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

The solution requires you to use a greedy algorithm (often implemented with a max‐heap) to always select the character with the highest remaining count that is not equal to the previously placed character. In cases where a valid rearrangement is not possible, you must output an empty string.

Note: If multiple rearrangements are possible, your program should produce the one that the algorithm deterministically generates.

For example, given the input aab, a valid output is aba.

inputFormat

The input consists of a single line containing the string S (1 ≤ |S| ≤ 10⁵). The string will consist of lowercase English letters.

Input is provided via standard input (stdin).

outputFormat

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

Output should be written to standard output (stdout).

aab

aba