# Rearrange String

Posted: 24 Dec, 2020
Difficulty: Easy

## PROBLEM STATEMENT

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

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
`````` Approach 1

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