 10

# Rearrange String

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

Problem Statement
Suggest Edit

#### 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