Last Updated: 24 Dec, 2020

Rearrange String

Easy

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

We will need the most frequent character at each step.
And to achieve this we can use the Max heap.
We will make a Max heap with characters and their frequencies sorted by frequency in descending order.
Now we will pop up the top two pairs from the heap, let first and second.
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.
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.
If the size of the heap is zero we will return the resultant string.
If the size of the heap is not equal to zero then it must have a single pair.
If the frequency of the last pair is equal to 1 then add that character to the resultant string and return the string.
If the frequency of the last pair is greater than 1, then no solution exists.

The steps are as follows:

Make a priority_queue as max heap let's say ‘MYPQ’.
Take an array of size 26 to store the frequency of each character.
Now traverse through the array and add character and its frequency in ‘MYPQ’ as a pair.
Let the final string is ‘ANS’ = ”” .
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.
If the size of MYPQ==0 returns ‘ANS’, else go to step 7.
Now check the frequency of the last element remaining.
1. If frequency > 0 : Return (empty string)
2. Else : Return s+LastPair’s -> character

Solve now

02 Approach

The required string is possible only when the frequency of the most frequent character is less than or equal to half of the size of the given string.

We can check the above-stated fact. Let's say we have a string of length 10. And say the most frequent character is ‘a’. Then the best possible way to arrange is ‘a_a_a_a_a_’. Now we can see if the frequency of a is greater than 5 then we can not make the required string. So we are going to store the frequency of each character and sort it. Let's say we name this array ‘HASH’.

Now if the frequency of the most frequent element is greater than half of the size of the given string. We can say no solution exists.
Make a new character array that will store the resulting string. Let's name it ‘ARR’.
Now assign the most frequent element on even positions(0 based indexing) from starting and make its frequency zero in ‘HASH’.
Now fill the remaining even positions with the characters whose ‘HASH’ > 0 keeping in mind if start filling a character make sure you use all of its occurrences in one go.
Now fill the remaining positions in any style with characters whose ‘HASH’>0.

The steps are as follows:

Let's say we have given a string ‘STR’. Take an array of size 26 and store frequency of characters let's say ‘HASH’.
Find which element of the array has maximum frequency let's say the element is ‘MXPOS’ and its frequency is ‘MXF’.
Make a char array of string size let's say ‘ARR’.
Check the following two case:
- If ‘MXF’ > (size of string +1)/2 : NO solution exists
- Else: for ‘i’ in 0 to ‘MXF’
  - ‘ARR[i]’ = ‘STR[MXPOS]’
  - Increase ‘i’ by 2.
  - Decrease frequency of ‘MXPOS’ by 1.

5. First fill the remaining even positions as we do in 2 of step 4.

6. Now we can fill the remaining odd positions in any order with the remaining characters.

Solve now