Rearrange String to Avoid Adjacent Duplicates

You are given a string s. Your task is to rearrange the characters of s so that no two adjacent characters are identical. If it is impossible to rearrange the string in such a manner, output an empty string.

The problem can be stated mathematically as follows: given a string \(s\) consisting of characters, find a permutation \(s'\) of \(s\) such that for all valid indices \(i\), \(s'_i \neq s'_{i+1}\). If no such rearrangement exists, return the empty string "".

Example:

• Input: aaabbc Output: ababac (one possible valid rearrangement)
• Input: aaabbb Output: ababab
• Input: aaaaaa Output: "" (impossible to rearrange)

Use an appropriate greedy algorithm (often implemented using a max-heap) to solve this problem efficiently.

inputFormat

The input consists of a single line containing the string s. The string can contain mixed case letters and other characters.

outputFormat

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

aaabbc

ababac