REARRSTR - Editorial

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

Easy

PREREQUISITES:

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:

Author’s solution
Tester’s solution

1 Like

@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)
please reply about my algo

@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…

Link to my solution: http://www.codechef.com/viewsolution/7019331

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

@angad_coder

Input:

3

a

bxbxbxbxy

azazazazazazazx

@drj_reddy Thanks

@adi28galaxyak

3
aaaaabbbbb
aabbccc
bab

plzz tell me how is that possible… range of t is t<10^5 , so the data type of t should be long int, but in the following solution it is solved with “int” only…??
http://www.codechef.com/viewsolution/7017858

I have been getting a wrong answer for my code.
http://www.codechef.com/viewsolution/7019853

I would be glad if someone could give me a test case for which this fails.

Here’s what i did. I implemented a Heap whose where the first 2 highest values are constantly updated. This is essentially a greedy approach since i take the 2 largest. So if it were aaabbc. It would take a nd b whose occurences are 3 and 2. It would reduce them to 2 and 1 respectively and append the character to a string. Now the heap essentially consists of a(2) b(1) c(1). Now remove a and b and repeat. Now you have a(1),c(1). Append and done. Also, be careful when the size of the heap is 1. E.i only one character is left. You can add it only if the number of occurences of that character are 1 and the previuos value appended is not equal to this one.

My code: http://www.codechef.com/viewsolution/7019973

can any one tell where i did wrong…
i am getting runtime error(nzec) but it is working good in my system for all cases…
http://www.codechef.com/viewsolution/7016382link text

@vedikaa Your solution fails here link text