Reorder String to Avoid Adjacent Duplicates

Given a string along with an expected length n, rearrange the string so that no two adjacent characters are identical. If such an arrangement is not possible, output Not possible.

The string consists only of lowercase English letters. Note that if the provided length n does not match the actual string length, the rearrangement is considered invalid and you should output Not possible.

You can solve this problem using a greedy algorithm with a max-heap (priority queue) to always choose the character with the highest remaining frequency that is not the same as the previously placed character.

inputFormat

The input consists of two lines:

• The first line contains an integer n representing the expected length of the string.
• The second line contains a string s of lowercase letters.

outputFormat

Output the rearranged string such that no two adjacent characters are identical. If no valid rearrangement exists, print Not possible.

1
a

a