Rearrange String to Avoid Adjacent Duplicates

You are given a string s and your task is to rearrange the characters of the string such that no two adjacent characters are the same. If such an arrangement is not possible, output an empty string.

For instance:

• For s = "aab", one valid rearrangement is "aba".
• For s = "aabc", valid rearrangements include "abac", "acba", "baca", or "caba".
• If no valid rearrangement exists, such as s = "aaab", output an empty string.

This problem requires careful handling of frequencies of characters and selecting the next most frequent character which is not equal to the previous one. The solution must be implemented using a greedy algorithm with a priority queue or equivalent data structure.

inputFormat

The input consists of a single line containing the string s.

Note: The string can include any characters, and its length is at least 1.

outputFormat

Output a single line that is the rearranged string meeting the criteria. If no valid rearrangement exists, output an empty string.

aab

aba