Reorganized String

You are given a string s consisting of lowercase letters. Your task is to rearrange the characters of s so that no two adjacent characters are the same. If it is not possible to form such a string, output an empty string.

One typical approach is to use a greedy algorithm with a priority queue (or max heap) to repeatedly choose the character with the highest remaining frequency that is not the same as the previously chosen character.

The problem is formally defined as follows:

Given a string \( s \) of length \( n \), rearrange the string to obtain a new string \( t \) such that for all \( 1 \leq i < n \), \( t_i \neq t_{i+1} \). If such a rearrangement is impossible, return the empty string.

inputFormat

The input consists of a single line containing the string s (a sequence of lowercase English letters).

outputFormat

Output a single line containing the rearranged string that meets the requirement, or an empty string if no valid arrangement exists.

aab

aba