10

Rearrange String

Difficulty: EASY
Avg. time to solve
15 min
Success Rate
85%

Problem Statement
Suggest Edit

You are given a string of lowercase characters. Your task is to rearrange (reorder) the string in such a way that no two adjacent characters are the same.

You have to return the rearranged string. If there exists more than one solution you can return any of them.If there is no such string you have to return “NO SOLUTION”. If your returned value is correct the program will print ‘CORRECT’ else ‘INCORRECT’.

For example :

If we are given a string ‘aabb’, then the possible solutions are:
(i) abab
(ii) baba
We can see no two adjacent characters are the same in both strings.
So both (i) and (ii) are valid solutions.
Input Format:
The first line of input contains a single integer T, representing the number of test    cases
Then the T test cases follow.

The first and only line of each test case contains a string STR.
Output format:
For each test case, return the resultant string if it is possible to rearrange string else return ‘NO SOLUTION’. Accordingly, CORRECT or INCORRECT will get printed on the screen.
The output of every test case will be printed in a separate line. 
Note
You don’t have to print anything, it has already been taken care of. Just implement the given function. 
Constraints:
1 <= T <= 100
1 <= N <= 10^4

Where ‘T’ is the number of test cases and ‘N’ is the length of the string.

Time limit: 1 second

Sample input 1:

3
aac 
azzz
abbc

Sample output 1

aca
NO SOLUTION
abcb

Explanation for sample output 1

(i) For the first string there exists only one solution which is ‘aca’. We can see no two adjacent characters are the same.
(ii) For the second string there exists no solution.
(iii) For the third string there exists more than one solution out of which ‘abcb’ is also a possible solution.

Sample input 2:

3
bbb 
xyz
yaxx

Sample output 2

NO SOLUTION
xyz
axyx

Explanation for sample output 2

(i) For the first string there exists no solution.
(ii) For the second string there exists more than one solution out of which ‘xyz’ is a possible solution.
(iii) For the third string there exists more than one solution out of which ‘axyx’ is a possible solution.
Want to solve this problem? Login now to get access to solve the problems