PROBLEM LINK:
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.
