Rearrange String to Avoid Adjacent Duplicates

Given a string ( S ) consisting only of the characters 'a', 'b', and 'c', your task is to rearrange the characters so that no two adjacent characters are the same. More formally, if the rearranged string is ( R ) with ( |R| = n ), then for every ( 0 \le i < n-1 ), ( R[i] \neq R[i+1] ). If such a rearrangement is possible, output any valid configuration; otherwise, output an empty string.

The problem requires careful handling of character frequencies, and a greedy algorithm using a priority queue (or similar data structure) is a typical approach to achieve this. The challenge lies in correctly determining when reordering is impossible and ensuring that the algorithm efficiently manages the characters' counts.

inputFormat

Input is provided via standard input (stdin) and consists of a single line containing the string ( S ) with characters chosen from {'a', 'b', 'c'}. There are no spaces in the input.

outputFormat

Output the rearranged string to standard output (stdout) such that no two adjacent characters are the same. If no valid rearrangement exists, output an empty string.## sample

aabb

abab