New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Rearrange string

Contributed by

Dhruv Sharma

Hard

0/120

50 mins

50 %

17 upvotes

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 )

Input format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

Then the T test cases follow.

The first line of each test case contains a string S.

Output format :

For each test case, the output will be “Yes” if you have returned the correct answer, else it will be “No”.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

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”.

Autocomplete

Console