Reorganize String

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

The solution must read input from standard input (stdin) and output the answer to standard output (stdout). In case of multiple valid rearrangements, the program should output the one determined by the algorithm described below.

The algorithm uses a greedy approach with a max heap. Let \( f(c) \) denote the frequency of character \( c \). The idea is to repeatedly choose the character with the highest remaining frequency that is not the same as the previously chosen character. If at any step no valid character exists but the string has not been fully rearranged, then output an empty string.

inputFormat

The input consists of a single line containing a non-empty string s whose characters need to be rearranged. The string is read from stdin.

outputFormat

Output a single line: the rearranged string such that no two adjacent characters are the same. If it is impossible to rearrange the string accordingly, output an empty string.

aab

aba