REARRSTR - Editorial



Author: Praveen Dhinwa
Tester: Utkarsh Lath
Editorialist: Balajiganapathi Senthilnathan
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng






Given a string s, can you rearrange it such that no two consecutive characters are equal? If yes, print any such rearrangement.


We will use the following greedy algorithm. At each position, the character we are going to put will be the one with highest frequency and is not equal to previous character.

In other words, count the frequency of each character. For each position, select the highest frequency character which is not equal to the previous character. Decrement the frequency of this character. If such a character does not exist for any position, then a rearrangement is not possible.


First we note that only the count of characters in the string s matters i.e. the initial order of characters in the string s does not matter.

Let us try to build the string from left to right. Intuitively, we want that the remaining highest frequency of the characters should be as low as possible (i.e. if a character has very high frequency, then it is tough for us to accommodate the no two consecutive equal characters condition).

So, for each position we will try to place the character with highest frequency such that it is not equal to previous character. If we have put all the characters in such way, then we are done. Otherwise we can prove that the arrangement is not possible and we output -1.

Time Complexity:

O (n)

Author’s Solution

Let us take a string s = “abbcc”. Now, in this example, we have a bad space between the two b’s and between the two c’s. In the corresponding string “ab-bc-c”, bad spaces are denoted by “-”. Formally, we define number of bad spaces as number of places where we should insert some character different from it’s previous and next one to make sure that string is valid.

Now, let us take most basic case for which it would be impossible to arrange the characters in the desired way. If the higest frequency character has size more than half of size the string, then it is impossible to construct the valid string because number of bad spaces by putting highest frequency frequency will be at least \lceil \frac{n}{2} \rceil.

Let us take the characters from in decreasing order of their frequency. Initially, we take the first character and put all its occurrences linearly. So, it we have total k characters, we will have k - 1 bad spaces initially. Now, iteratively, we will reduce number of bad spaces.
Now, we will take the next character and by using it, first we will first greedily remove as many bad spaces as possible. Now, if all the bad spaces are removed, then, we will try to create least amount of bad spaces as possible. Note that this process will reduce number of bad spaces strictly. As, you are processing characters one by one, and for a fixed character, you can have at most \mathcal{O}(n) time. So total time will be \mathcal{O}(26 * n) which will fit in the time. Please see author’s solution from for more details.


Author’s solution
Tester’s solution

1 Like

Please someone help me find out for which case my solution gives wrong answer. I tried so many cases but didn’t find such case.

Try aabbc …

1 Like

Can anyone please give me a testcase where my solution fails ?
my solution

please give me test case where my solution gives wa

Please someone help me find out for which case my solution gives wrong answer. I tried so many cases but didn’t find such case. GIVES WA… have approached the same way as is mentioned above… Need test case where it fails…? :frowning:

Fails in this case: aabbccc

link text this one gave me NZEC. Any idea how the exception was thrown, maybe Array out of bounds, or some other

is this algorithm is correct
sort each in increasing order of frequency then
place first letter with highest frequency at position k=(ceil)length/frquency means a[0].a[0+k-1]…etc and place all the other alphabets just after each highest frequency word
eg aaabbcc firstly ( a a a ) then ( ab ab a ) then ( abcabca)
please reply about my algo

Your code fails for case : abb

can you check why my algorithm is showing time limit exceeded? can someone tell me a non-working test case?

can someone pl give a test case where my code fails??

can someone give me a test input where my code is failing…

Link to my solution:

@vagar19 Case: azzzz This is my solution which got time limit exceeded.Can anyone help me with this?I think time complexity is O(n).







@drj_reddy Thanks