Reorder String to Avoid Adjacent Duplicates

You are given a string s consisting of lowercase letters. Your task is to rearrange the characters of s such that no two adjacent characters are the same.

If such a rearrangement is possible, print the rearranged string. Otherwise, print an empty string.

Formally, for a string \( s \) of length \( n \), find a permutation \( t = t_1t_2\ldots t_n \) of \( s \) such that \( t_i \neq t_{i+1} \) for every \( 1 \le i < n \). If no such permutation exists, output an empty string.

A common approach for this problem is to use a greedy algorithm with a max heap to always choose the character with the highest remaining frequency that is not equal to the previously chosen character. This method typically runs in \( O(n \log n) \) time.

inputFormat

The input consists of a single line containing the string s (\( 1 \leq |s| \leq 10^5 \)), which is composed only of lowercase English letters.

outputFormat

Output a single line with the rearranged string such that no two adjacent characters are the same. If it is not possible to rearrange s in this way, output an empty string.

## sample

aabb

abab

</p>