Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Rearrange string

Hard
0/120
Average time to solve is 50m
33 upvotes
Asked in companies
eBayAdobeMicrosoft

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”.
Full screen
Console