# REARRSTR - Editorial

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

Easy

Greedy

### PROBLEM:

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

### SHORT EXPLANATION

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.

### EXPLANATION:

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 AND TESTERâ€™S SOLUTIONS:

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.
http://www.codechef.com/viewsolution/7018772

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
http://www.codechef.com/viewsolution/7018600

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. http://www.codechef.com/viewsolution/7018087

http://ideone.com/kmxyYA GIVES WAâ€¦ have approached the same way as is mentioned aboveâ€¦ Need test case where it failsâ€¦?

@rajeshgmax
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)

@debverine
Your code fails for case : abb

can you check why my algorithm is showing time limit exceeded?

http://www.codechef.com/viewsolution/7019362 can someone tell me a non-working test case?

can someone pl give a test case where my code fails??
http://www.codechef.com/viewsolution/7018861

can someone give me a test input where my code is failingâ€¦

@vagar19 Case: azzzz

http://www.codechef.com/viewsolution/7018412 This is my solution which got time limit exceeded.Can anyone help me with this?I think time complexity is O(n).

Input:

3

a

bxbxbxbxy

azazazazazazazx

@drj_reddy Thanks

//