Reorganize String

You are given a string s consisting of lowercase English letters. Your task is to rearrange the characters of the string so that no two adjacent characters are the same.

If such a reorganization is possible, print one valid rearrangement. Otherwise, print an empty string.

The solution must follow a greedy approach utilizing a max‐heap (priority queue) and, when frequencies tie, choose the lexicographically smallest character. The algorithm works in O(n log k) time where n is the length of the string and k is the number of distinct characters. In mathematical terms, if the frequency of a character c is \(f(c)\), then a solution is possible only if \[ f(c) \leq \left\lceil \frac{n}{2} \right\rceil \quad \text{for all characters } c. \]

inputFormat

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

outputFormat

Output the reorganized string such that no two adjacent characters are the same. If it is impossible to reorganize, output an empty string.

aab

aba