# Rearrange a string so that no two adjacent characters have the same letter

In this article, we are going to see **how we can reorganize a string using a heap so that no two adjacent characters become the same?**

Submitted by Radib Kar, on September 15, 2020

**Prerequisite:**

In this article, we are going to see how we can use a heap data structure to rearrange a string so that no two adjacent characters are the same. If the rearrangement is possible then return the rearranged string as output and if no such rearrangement is possible then return an empty string or a prompt message that no such string is possible.

For example,

If the input string is "aabbcc" then one possible rearrangement would be "abcabc" which follows the constraints.

If the input string is "aaab" then no rearrangement is possible which follows the constraint. To validate the possible rearrangements are:

"abaa", "aaba", "baaa" etc.

**Solution**

**1) Brute Force**

The brute force solution is about generating all combinations and checking whether any of that follows the constraint. But if the string length is huge, then the brute force approach would be computationally very expensive and we can't entertain that.

**2) Efficient approach using a max heap**

The idea is to use a max heap to store characters with their frequencies. So we first create a hash table with the number of occurrences of each character and then create a max heap using the entries of the hash map. Of course, the heap creation criteria is frequency. So the root of the heap will be the letter having a maximum frequency. This part is the same as we did in my article on sorting based on frequency using lambda function. Please go through the pre-requisite article first as I am going to skip the detail of this implementation here.

So, after we have our max heap ready,

- We pop the top element from the heap which is the character with the max frequency one
- If the popped character is same as the last character of the partially rearranged string(if it's the first iteration, then we don't have to bother about this since this is the initial step for rearrangement), then we need to pop the current max frequent character which is the top of the current max heap. If this pop is possible, then we append the second popped character to the partially rearranged string, otherwise, the rearrangement is not possible as we have no second choice and need to append the same character as of the last character of the partially rearranged string.
- Keep repeating until the heap becomes empty.

Below is the implementation of the above algorithm and then we will check the dry run.

#include <bits/stdc++.h> using namespace std; string reorganizeString(string S) { //create the hash table unordered_map<char, int> hash; for (char it : S) { hash[it]++; } //lambda function as user-defined comparator auto comp = [](pair<char, int> a, pair<char, int> b) { if (a.second < b.second) return true; else if (a.second > b.second) { return false; } else { return a.first < b.first; } }; //max heap based on frequency priority_queue<pair<char, int>, vector<pair<char, int> >, decltype(comp)> q(comp); //create the max heap first for (auto & [ k, v ] : hash) { q.push(make_pair(k, v)); } ///////////////here starts rearrangement//////////////// //initially the result string is empty string result = ""; //while the heap is not empty while (!q.empty()) { //extract the top pair <char, frequency> char a = q.top().first; int b = q.top().second; q.pop(); //if this is the initial step of rearrangement simply append the character if (result.length() == 0) { result += string(1, a); //reduce the frequency and insert back into the heap b--; if (b != 0) { q.push(make_pair(a, b)); } } else { //if the rearrangement is started and done partially if (result[result.length() - 1] == a) { //if the last character in the rearranged string is same as the current top character //if there is no more option then the rearrangement is impossible if (q.empty()) return ""; //return empty string in that case //otherwise extract the current maximum frojm heap which is besically the second maximum char c = q.top().first; int d = q.top().second; q.pop(); //insert the first max back to heap q.push(make_pair(a, b)); //append the second max character to the partially rearranged string result += string(1, c); //reduce the frequency and insert back into the heap d--; if (d != 0) { q.push(make_pair(c, d)); } } else { //if the last character in the rearranged string is not same as the current top character //simply append to partially rearranged string result += string(1, a); //reduce the frequency and insert back into the heap b--; if (b != 0) { q.push(make_pair(a, b)); } } } } return result; } int main() { string str; cout << "Eneter input string:\n"; cin >> str; string result = reorganizeString(str); if (result == "") { cout << "No such rearrangement is possible\n"; } else cout << "One possible rearrangement is: " << result << endl; return 0; }

**Output:**

RUN 1: Eneter input string: aabbcc One possible rearrangement is: cbacba RUN 2: Eneter input string: aaab No such rearrangement is possible

**Dry Run:**

Example 1: Input string: "aabbcc" After creating the heap, Key Frequency 'c' 2 'b' 2 'a' 2 Initially, result is "" 1st iteration: Extract 'c' (max/top one) Since result is empty, append to result, so it's now "c" Decrement frequency by 1 & Insertback to the heap So heap now: Key Frequency 'b' 2 'a' 2 'c' 1 2nd iteration: Extract 'b' result is not empty, but the last character in result is not the same as 'b', so append 'b' to result, so it's now "cb" Decrement frequency by 1 & Insert back to the heap So heap now: Key Frequency 'a' 2 'c' 1 'b' 1 3rd iteration: Extract 'a' result is not empty, but the last character in result is not the same as 'a', so append 'a' to result, so it's now "cba" Decrement frequency by 1 & Insert back to the heap So heap now: Key Frequency 'c' 1 'b' 1 'a' 1 4th iteration: Extract 'c' result is not empty, but the last character in result is not the same as 'c', so append 'c' to result, so it's now "cbac" Decrement frequency by 1, since the frequency is now 0, no need to insert it back to the heap So heap now: Key Frequency 'b' 1 'a' 1 5th iteration: Extract 'b' result is not empty, but the last character in result is not the same as 'b', so append 'b' to result, so it's now "cbacb" Decrement frequency by 1, since the frequency is now 0, no need to insert it back to the heap So heap now: Key Frequency 'a' 1 6th iteration: Extract 'a' result is not empty, but the last character in result is not the same as 'a', so append 'a' to result, so it's now "cbacba" Decrement frequency by 1, since the frequency is now 0, no need to insert it back to the heap So heap now: empty Since the heap is empty the iteration stops and the result is "cbacba"

Please go ahead and perform then dry run for the second example and you will find that in the partial rearrangement the last character would be same as the max character in some step where you won’t have the second choice. So it will be impossible to rearrange the second example string.

Comments and Discussions!