Rearrange String Without Adjacent Duplicates

You are given a string s. Your task is to rearrange the characters of s so that no two adjacent characters are the same. If it is not possible to rearrange the string in such a fashion, output "Not Possible".

The intended solution uses a greedy algorithm with a max heap. In terms of complexity, if the frequency of characters is represented by a function \(f(c)\), the approach is to repeatedly choose the character with the highest remaining frequency that does not equal the previously added character. The correctness is based on the idea that if the most frequent character can always be postponed until a different character is placed, a valid rearrangement exists.

inputFormat

The first line contains an integer T representing the number of test cases. Each of the next T lines contains a non-empty string s consisting of lowercase English letters.

For example:

3
aab
aaab
aabbcc

outputFormat

For each test case, output a single line containing the rearranged string such that no two adjacent characters are the same. If no such rearrangement is possible, output "Not Possible".

For the sample input above, one valid output is:

aba
Not Possible
abcabc

1
aab

aba