Home » Data Structure

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:

• User-defined comparator for priority queue
• Sort elements by frequency

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,

1. We pop the top element from the heap which is the character with the max frequency one
2. 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.
3. 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 & Insert  back 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.