Rearrange String Problem Statement

Given a string ‘S’, your task is to rearrange its characters so that no two adjacent characters are the same. If it's possible, return any such arrangement, otherwise return “not possible”.

Example:

Input:

S = "qaacde"

Output:

"qacade"

Explanation:

In the string "qaacde", originally there are two same adjacent characters. One possible rearrangement where no two adjacent characters are the same is "qacade".

Input:

T
S1
S2
…
ST

Output:

"Yes" if rearrangement is possible, otherwise "No" for each test case.

Constraints:

• 1 <= T <= 10
• 0 <= |S| <= 10⁵
• Time Limit: 1 second.

Note:

No need to print anything; implementation of the function is sufficient.