# Rearrange string

Hard
0/120
Average time to solve is 50m

## Problem statement

You are given a string “S”. Your task is to rearrange the characters of a string “S”, such that it does not contain any two adjacent characters which are the same.

If it is possible to rearrange the string “S”, then print any possible arrangement. else, print “not possible” without quotes.

For Example:

``````For a string  “qaacde”, This string has two same adjacent characters.
So, one possible way to rearrange the string is “qacade”. Now, this string does not have two adjacent characters that are the same.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints :
``````1 <= T <= 10
0 <= |S| <= 10^5

Time Limit: 1 sec
``````
##### Sample Input 1 :
``````2
coding
abaab
``````
##### Sample Output 1 :
``````Yes
Yes
``````
##### Explanation :
``````For the first test case, the given string is “coding”. This string does not have two adjacent characters that are the same. So if we return “coding", then we will get an output as “Yes”.

For the second test case, the given string is “abaab”. This string has two adjacent characters that are the same i.e. abaab,  So we can rearrange the string as “ababa”.Hence we return “ababa”, then we will get an output as "Yes”.
``````
##### Sample Input 2 :
``````1
bbbbbb
``````
##### Sample Output 2 :
``````Yes
``````
##### Explanation :
``````For the first test case, the given string is “bbbbbb”. No matter how you rearrange characters of string , it will always remain the same as bbbbbb.So we return “not possible” as an answer, then we will get an output as ‘Yes”.
``````
Console