Rearrange String to Avoid Adjacent Repeating Characters

You are given a string S. Rearrange the characters of S so that no two adjacent characters are the same. If such a rearrangement is impossible, output an empty string.

The problem can be formalized as follows: Given a string \(S\) of length \(n\), rearrange its characters to form a string \(T\) such that for every \(1 \leq i < n\), \(T_i \neq T_{i+1}\). If no such string exists, return the empty string "".

Note: There can be multiple valid answers. In this problem, your solution is expected to produce one valid rearrangement if it exists.

inputFormat

The input is read from standard input. It consists of a single line containing a non-empty string S (with no spaces) that represents the characters to be rearranged.

Constraints:

• \(1 \leq |S| \leq 10^5\)
• S consists of printable ASCII characters.

outputFormat

Output to standard output a single line containing the rearranged string such that no two adjacent characters are the same. If no valid rearrangement exists, output an empty string.

aabb

abab