Rearrange String

Given a string s consisting of lowercase English letters, rearrange the characters of s so that no two adjacent characters are the same. If such an arrangement is not possible, output Not possible.

The idea behind the solution is to use a greedy algorithm combined with a max heap (or priority queue) to iteratively choose the character with the highest remaining frequency that is not equal to the previously used character.

Mathematically, if we denote the frequency of character i by \(f_i\) and the total length of the string by \(n\), a necessary condition for a valid rearrangement is:

[ \max_{i}(f_i) \leq \left\lceil \frac{n}{2} \right\rceil ]

If the above condition is not met, then the output should be Not possible.

inputFormat

The input consists of a single line containing the string s (1 \leq |s| \leq 10^5), which is composed of lowercase English letters.

outputFormat

Output a single line containing the rearranged string such that no two adjacent characters are the same. If no valid rearrangement exists, output Not possible.

aabb

abab