'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Topics

Rearrange String

Easy
0/40
Average time to solve is 15m
profile
Contributed by
133 upvotes
Asked in companies
IBMExpedia GroupAmazon

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