Rearrange String to Avoid Adjacent Duplicates

Given a string (s), rearrange its characters so that no two adjacent characters are the same. If such an arrangement is not possible, output "Not Possible".

The approach typically uses a greedy algorithm along with a priority queue (max heap) to repeatedly select the character with the highest remaining frequency that is different from the previously placed character. This ensures that the most frequent characters are distributed evenly.

The input consists of a single line containing the string (s), provided via standard input. Output a single line containing the rearranged string that meets the above condition. If it is impossible to rearrange (s) to satisfy the constraint, print "Not Possible".

For example, if (s = "aab"), one possible valid answer is "aba". Use the LaTeX format for any mathematical expressions (e.g. (n) for the length of the string).

inputFormat

A single line containing the string (s).

outputFormat

Print a single line containing the rearranged string. If it is not possible to obtain such a string, print "Not Possible".## sample

aab

aba