Reorganize String

You are given a string s consisting of lowercase letters. Your task is to rearrange the characters of s so that no two adjacent characters are identical. If such an arrangement is possible, output one valid rearrangement; otherwise, output an empty string.

One necessary condition for a valid reorganization is that the frequency of any character should not exceed \( \lceil \frac{n}{2} \rceil \), where \(n\) is the length of the string. For example, if the frequency of some character is greater than \( \frac{n+1}{2} \) then a valid rearrangement does not exist.

This is a classic greedy problem which can be solved using a max heap (priority queue) to always choose the character with the highest remaining count that is not equal to the previously placed character.

inputFormat

Input is given from standard input and consists of a single line containing the string s (only lowercase letters).

outputFormat

Output to standard output a valid reorganized string such that no two adjacent characters are the same. If no such rearrangement exists, output an empty string.## sample

aab

aba