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. Return 'Yes' if possible, 'No' otherwise.

Iterate through the string and count the frequency of each character
Use a priority queue to rearrange characters based on frequency
Check if the rearranged string has no two adjacent characters the same
Return 'Yes' if possible, 'No' otherwise