Reorganize String

You are given a string s consisting of lowercase letters. The task is to rearrange the characters of the string so that no two adjacent characters are the same. If it is not possible to achieve such an arrangement, print an empty string.

For example, given the string "aab", one valid answer is "aba". However, if the string does not have a valid arrangement (for instance, "aaab"), your program should output an empty string.

Note: If there are multiple valid answers, any one of them is accepted. The algorithm behind the solution typically involves using a max-heap (or priority queue) to repeatedly select the most frequent character and ensure that the same character is not used consecutively.

Mathematical Constraint: A valid rearrangement exists if and only if for every character, its frequency does not exceed \(\lceil \frac{n}{2} \rceil\), where \(n\) is the length of the string.

inputFormat

A single line containing the string s.

outputFormat

Print the rearranged string where no two adjacent characters are the same. If no valid rearrangement exists, print an empty string.## sample

aab

aba