Reorganize String

Given a string s, rearrange its characters so that no two adjacent characters are the same. If such a rearrangement is impossible (i.e. if some character appears more than \(\lceil \frac{n}{2} \rceil\) times, where \(n\) is the length of s), output an empty string.

You are required to read the input from standard input (stdin) and output the result to standard output (stdout). The problem tests your ability to use greedy algorithms with a priority queue (or heap) data structure.

inputFormat

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

outputFormat

If a valid rearrangement exists, output the rearranged string such that no two adjacent characters are the same. Otherwise, output an empty string.

aab

aba