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
S₁
S₂
…
S_T

Output:

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

Constraints:

1

Question

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
S₁
S₂
…
S_T

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.

Accepted Answer

Given a string, rearrange its characters so that no two adjacent characters are the same.

Iterate through the string and count the frequency of each character.
Use a priority queue to rearrange the characters based on their frequency.
Check if it's possible to rearrange the string without any two adjacent characters being the same.
Return 'Yes' if possible, 'No' otherwise.