Rearrange String

Easy
0/40
Average time to solve is 15m
profile
Contributed by
144 upvotes
Asked in companies
AmazonIBMExpedia Group

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

Think about the greedy approach like will it be helpful if we start making a new string and at each step, we know the current most frequent element.

Approaches (2)
Greedy Approach

 

  1. We will need the most frequent character at each step.
  2. And to achieve this we can use the Max heap.
  3. We will make a Max heap with characters and their frequencies sorted by frequency in descending order.
  4. Now we will pop up the top two pairs from the heap, let first and second.
  5. Add the first pair’s character in a new string and decrease its frequency by 1 and if its frequency is >0 push it to the heap.
  6. Add the second pair’s character in the new string and decrease its frequency by 1 and if its frequency is >0 push to the heap.
  7. If the size of the heap is zero we will return the resultant string.
  8. If the size of the heap is not equal to zero then it must have a single pair.
  9. If the frequency of the last pair is equal to 1 then add that character to the resultant string and return the string.
  10. If the frequency of the last pair is greater than 1, then no solution exists.

 

The steps are as follows:

 

  1. Make a priority_queue as max heap let's say ‘MYPQ’.
  2. Take an array of size 26 to store the frequency of each character.
  3. Now traverse through the array and add character and its frequency in ‘MYPQ’ as a pair.
  4. Let the final string is ‘ANS’ = ”” .
  5. While size of ‘MYPQ’ > 1 :
    • Let first = ‘MYPQ’ -> top
    • Pop up ‘MYPQ’.
    • Let second = ‘MYPQ’ -> top
    • Pop up ‘MYPQ’.
    • ‘ANS’ += first -> character , ‘ANS’ += second -> character
    • Decrease the frequency of first and second by 1.
    • If the frequency of first or second greater than 0 pushes that to ‘MYPQ’.
    • Decrease the size of ‘MYPQ’ by 1.
  6. If the size of MYPQ==0 returns ‘ANS’, else go to step 7.
  7. Now check the frequency of the last element remaining.
    1. If frequency > 0 :  Return (empty string)
    2. Else  : Return s+LastPair’s -> character
Time Complexity

O(N), Where ‘N’ is the length of the string.

 

Since the actual time complexity is O(N * log(A)) for the priority_queue we are using where A is the number of different alphabets which in our case is 26(a constant). Thus the time complexity will be O(N).

Space Complexity

O(1). 

 

Since the actual time complexity is O(A) where A is the number of different alphabets which in our case is 26(a constant). Thus the space complexity will be O(1). 

Code Solution
(100% EXP penalty)
Rearrange String
Full screen
Console