Rearrange String to Avoid Adjacent Duplicates

Given a string ( s ), rearrange the characters so that no two adjacent characters are the same. If there is no valid rearrangement, output an empty string. This problem can be modeled using a greedy approach with a max-heap. The method ensures that the most frequent character is placed as far apart as possible. Formally, if a character ( x ) appears ( f_x ) times in ( s ), a valid rearrangement exists only if ( f_x \leq \left\lceil \frac{n}{2} \right\rceil ), where ( n ) is the length of ( s ).

inputFormat

A single line of input is given from stdin which contains the string ( s ) to be rearranged.

outputFormat

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

aab

aba