Rearrange String

Easy

0/40

Average time to solve is 15m

Contributed by

138 upvotes

Asked in companies

Problem statement

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.

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.

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.

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 ‘N’ is the length of the string.

Time limit: 1 sec

Sample Input 1:

3
aac 
azzz
abbc

Sample Output 1:

aca
NO SOLUTION
abcb

Explanation for Sample Output 1:

In test case 1, there exists only one solution which is ‘aca’. We can see no two adjacent characters are the same.

In test case 2, For the second string there exists no solution.

In test case 3, 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:

In test case 1, there exists no solution.

In test case 2, there exists more than one solution out of which ‘xyz’ is a possible solution.

In test case 3, there exists more than one solution out of which ‘axyx’ is a possible solution.

Console