Reorder String to Avoid Adjacent Duplicates

Given a string s consisting of lowercase English letters, your task is to reorder the characters of the string so that no two adjacent characters are the same. If such a reordering is possible, output any one valid rearrangement; otherwise, output an empty string.

Note: The solution may not be unique. However, the output must satisfy the condition that no two adjacent characters in the string are identical.

Mathematically, if we denote the frequency of each character c by \(f(c)\) and the total length of the string by \(n\), a necessary condition for a valid solution is that for every character c, \[ f(c) \leq \left\lceil \frac{n}{2} \right\rceil. \] If this condition is violated, the solution does not exist and the output should be an empty string.

inputFormat

The input is provided via stdin as a single line that contains the string s, consisting only of lowercase English letters.

outputFormat

Output the reordered string via stdout. If it is not possible to reorder the string such that no two adjacent characters are the same, output an empty string.

aab

aba