Rearrange String to Avoid Adjacent Duplicates

Given a string s consisting of lowercase English letters, rearrange the characters of s so that no two adjacent characters are the same. If such a rearrangement is possible, output one valid rearrangement; otherwise, output an empty string.

The solution should use a greedy strategy, for example by using a max-heap (priority queue) to always choose the most frequent character that is not equal to the previously placed character. Formally, if the frequency of any character exceeds \( \lceil \frac{n}{2} \rceil \) where \( n \) is the length of the string, the rearrangement is impossible.

inputFormat

The input is provided via standard input and consists of a single line containing the string s (possibly empty) composed of lowercase English letters.

outputFormat

Output a valid rearranged string via standard output such that no two adjacent characters are the same. If no such rearrangement is possible, output an empty string.

aab

aba