Rearrange String to Avoid Adjacent Repetition

Given a string s, rearrange its characters so that no two adjacent characters are the same. If a rearrangement satisfying this condition is not possible, output an empty string.

The problem requires an efficient solution that can handle large inputs. One common approach is to use a max-heap (or priority queue) to always choose the character with the highest remaining frequency that is not the same as the previously placed character. In mathematical terms, if the frequency of a character c is \( f(c) \), a valid rearrangement exists if and only if:

\( \max_{c \in s} f(c) \leq \left\lceil\frac{|s|}{2}\right\rceil \)

inputFormat

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

outputFormat

Output a rearranged string where no two adjacent characters are the same. If no such arrangement exists, output an empty string.

aaabb

ababa