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 such an arrangement is not possible, print Not Possible.

More formally, if the rearranged string is denoted by t, then it must hold for all indices \(i\) (with \(1 \le i < n\)) that:

\(t_i \neq t_{i+1}\)

If multiple answers exist, output any one of them. The input string may contain repeated characters. The solution should use greedy techniques with priority queues (or equivalent methods) to ensure each step picks the most frequent valid character.

inputFormat

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

\(\textbf{Constraints:}\)

• 1 \(\leq \text{length of } s \leq 10^5\)
• s consists of English letters.

outputFormat

Output a rearranged string where no two adjacent characters are the same. If it is impossible to rearrange s to meet the requirement, output Not Possible (without quotes).

a

a