Reorganize String to Avoid Adjacent Duplicates

Given a string (s), rearrange its characters so that no two adjacent characters are the same. If such a reorganization is impossible, output an empty string.

The problem can be solved using a greedy algorithm with a priority queue. Specifically, at each step, choose the character with the highest remaining frequency that is not identical to the previously placed character. If no such character exists and the string is not fully reorganized, then a valid rearrangement is impossible.

For example, if (s = \text{'aab'}), one valid output is (\text{'aba'}); however, if (s = \text{'aaab'}), no valid reorganization exists, and you should output an empty string.

inputFormat

The input is given via standard input. It consists of a single line containing the string (s).

outputFormat

Print the reorganized string on standard output. If no valid reorganization exists, print an empty string.## sample

aab

aba