Reorganise a string with a max heap

Why this matters

Some outputs must spread similar items apart. A playlist should not play the same artist twice in a row. A seating plan should not put two members of the same group side by side. A string of letters may need the same rule. The task in this lesson is a small version of that problem: given the letters of a word, rearrange them so that no two equal letters touch.

The problem teaches a greedy method, which means making the best choice at each step and never going back. The choice is made with a max heap. A max heap is a tree stored in an array where the largest item is always on top. In C++ the standard std::priority_queue is a max heap by default. The heap here holds pairs of (how many copies are left, which letter), so the top is always the letter that still has the most copies.

The lesson also covers the case where no answer exists. Some letter sets cannot be arranged at all, and the program must say so. Finding that out quickly is part of the lesson.

The rule in plain words

Two letters are neighbours when they sit next to each other in the string. The rule is that no two neighbours may be the same letter.

Take the input aaabbc. The letter a appears three times, b twice, and c once. One output that follows the rule is abacba. Check each pair of neighbours: ab, ba, ac, cb, ba. None of them is a repeat. The output uses each letter the same number of times as the input, so it is a rearrangement.

Now take aaab. Three a letters and one b cannot be placed with no two a letters touching. Every arrangement has a pair of a letters next to each other. So the answer for this input is that no valid string exists.

The idea: the hardest letter goes first

The letter with the most copies is the hardest one to space out. Each copy must have a different letter after it, so a letter with many copies needs many gaps. If we leave that letter until the end, there may be no gaps left.

So the method works like this. At each step, place the letter that has the most copies left. The one exception is the letter we just placed. That letter may not go next, because it would touch itself. So we hold it aside for one step, and then return it to the heap.

Here is the rule written as steps.

1. Take the letter with the most copies left from the heap. Call it x, and call its count c.
2. Append x to the output.
3. If a letter was held from the previous step and it still has copies left, put it back into the heap.
4. Hold x for the next step, with c - 1 copies left.
5. Go back to step 1 while the heap is not empty.

Step 3 comes before step 4 on purpose. The letter held from the previous step is not in the heap while step 1 runs, so the heap can never offer it again right away. That is what keeps two equal letters apart.

When the heap is empty, the held letter is the last one left. If it still has copies, there is nowhere to put them, and the answer is impossible.

A trace on paper

Let us follow the steps on aaabbc. The heap starts with a 3 times, b 2 times, and c once. Nothing is held at the start, so the table shows the held letter as none.

At step 2, the held letter a is pushed back into the heap before the next pick. At step 4, the heap holds b and c, each with one copy, and c wins the tie because the pair is compared by letter when counts are equal. At step 5 the held letter is c with no copies left, so nothing is pushed back.

The final output is abacba, which matches the trace we will print from the program.

Building it with a max heap

Here is the method in C++. The verbose flag prints the output after each step, so the trace above can be checked by running the program.

#include <array>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
using namespace std;
 
// Returns an empty string when no arrangement exists.
string reorganize(const string& s, bool verbose = false) {
    array<int, 26> freq{};
    for (char c : s) freq[c - 'a']++;
 
    priority_queue<pair<int, char>> heap;  // (copies left, letter); most copies first
    for (int i = 0; i < 26; ++i)
        if (freq[i] > 0) heap.push({freq[i], static_cast<char>('a' + i)});
 
    string out;
    pair<int, char> held{0, '?'};  // letter placed last step; it must wait one turn
    while (!heap.empty()) {
        auto [copies, letter] = heap.top();
        heap.pop();
        out += letter;
        if (held.first > 0) heap.push(held);
        held = {copies - 1, letter};
        if (verbose) cout << "placed " << letter << ", output is now " << out << "\n";
    }
    if (held.first > 0) return "";
    return out;
}
 
int main() {
    string result = reorganize("aaabbc", true);
    cout << "answer " << result << "\n";
}

Compile it with g++ -std=c++20 -Wall, run it, and it prints:

placed a, output is now a
placed b, output is now ab
placed a, output is now aba
placed c, output is now abac
placed b, output is now abacb
placed a, output is now abacba
answer abacba

The copies variable is copied out of the heap with the structured binding auto [copies, letter] = heap.top();. The copy is made before pop(), so the values are safe to use after the pop. Some other lines are worth reading closely.

• array<int, 26> freq{}; makes 26 counters, all set to zero. The letter 'a' uses index 0, 'b' uses index 1, and so on, by subtracting 'a' from the letter.
• held.first > 0 asks whether the held letter still has copies. The first field is the count, and second is the letter.
• held = {copies - 1, letter}; stores the letter just placed, with one copy fewer, so the next step can see it.
• The function returns an empty string for the impossible case. The caller tests it with result.empty(). A non-empty input that has an answer never returns an empty string.

Why the held letter is enough

The method only looks one step back. Why is that enough?

At each step only the held letter is blocked. Every other letter in the heap is allowed, and the top of the heap is the letter with the most copies. So the heaviest letter is always placed early, while there is still room for it.

The method also gives a clear test for impossibility. Take a string of n letters. The largest set of positions that do not touch each other is the odd positions 1, 3, 5, and so on. That set has (n + 1) / 2 positions, using whole-number division. For n equal to 4, that is 2. For n equal to 5, that is 3. A letter with more copies than that cannot avoid touching itself.

So the answer is possible when the most common letter satisfies

largest count <= (n + 1) / 2

Worked examples of increasing difficulty

The first example is the simplest. Take aab. The heap has a with two copies and b with one. The method places a, holds it, then places b, pushes a back, and places a again. The output is aba. Here n is 3, and the largest count is 2, which is at most (3 + 1) / 2 = 2, so the answer is possible.

The second example is the trace from earlier. aaabbc has n equal to 6, and the largest count is 3. The test gives (6 + 1) / 2 = 3, and 3 is at most 3, so the answer is possible. The method produces abacba.

A second medium example is vvvlo. It has three v letters, one l and one o. The test gives (5 + 1) / 2 = 3, and v has three copies, so an answer exists. Follow the heap in order.

1. The top is v with 3 copies. Place v, and hold it with 2 copies left. The heap holds l and o, each with 1 copy.
2. The top is o, because o is larger than l when the counts tie. Place o. Push the held v back, so the heap holds v with 2 copies and l with 1. Hold o with none left.
3. The top is v. Place v, and hold it with 1 copy left. Nothing is pushed back, because the held o had none left.
4. The heap holds only l, with 1 copy, because the held v is not in the heap yet. Place l. Push the held v back, so the heap holds v with 1 copy. Hold l with none left.
5. The top is v, its last copy. Place it. Nothing is held with copies left and the heap is empty, so the loop ends.

The output is vovlv. The three v letters take positions 1, 3 and 5, the only three positions in a string of five that do not touch.

The third example is harder, because the most common letter fills every odd position exactly. Take aaaabbbc. Here n is 8, and a has four copies. The test gives (8 + 1) / 2 = 4, and 4 is at most 4, so an answer exists. The method produces ababacba. Count the letters: a appears four times, b three times, and c once. No two neighbours are equal.

Take aaaaabbb as the impossible case. Here n is 8, and a has five copies. The test gives (8 + 1) / 2 = 4, and 5 is greater than 4, so no answer exists. The method reaches the end with a held and one copy left, and it returns an empty string.

The program below runs these cases. It also checks 300,000 random inputs. For each one, it confirms that the answer is valid when the formula says it is possible, and that the answer is empty when the formula says it is not.

#include <algorithm>
#include <array>
#include <iostream>
#include <queue>
#include <random>
#include <string>
#include <utility>
using namespace std;
 
// Returns an empty string when no arrangement exists.
string reorganize(const string& s) {
    array<int, 26> freq{};
    for (char c : s) freq[c - 'a']++;
 
    priority_queue<pair<int, char>> heap;  // (copies left, letter); most copies first
    for (int i = 0; i < 26; ++i)
        if (freq[i] > 0) heap.push({freq[i], static_cast<char>('a' + i)});
 
    string out;
    pair<int, char> held{0, '?'};
    while (!heap.empty()) {
        auto [copies, letter] = heap.top();
        heap.pop();
        out += letter;
        if (held.first > 0) heap.push(held);
        held = {copies - 1, letter};
    }
    if (held.first > 0) return "";
    return out;
}
 
bool possibleFormula(const string& s) {
    array<int, 26> freq{};
    for (char c : s) freq[c - 'a']++;
    int maxFreq = *max_element(freq.begin(), freq.end());
    return maxFreq <= (static_cast<int>(s.size()) + 1) / 2;
}
 
bool isValid(const string& original, const string& result) {
    if (result.size() != original.size()) return false;
    array<int, 26> a{}, b{};
    for (char c : original) a[c - 'a']++;
    for (char c : result) b[c - 'a']++;
    if (a != b) return false;
    for (size_t i = 1; i < result.size(); ++i)
        if (result[i] == result[i - 1]) return false;
    return true;
}
 
int main() {
    for (string s : {"aab", "aaabbc", "aaaabbbc", "aaaaabbb"}) {
        string r = reorganize(s);
        cout << s << " -> " << (r.empty() ? "(impossible)" : r) << "\n";
    }
 
    mt19937 rng(5);
    int bad = 0, possible = 0;
    for (int it = 0; it < 300000; ++it) {
        int letters = 1 + rng() % 5, len = 1 + rng() % 14;
        string s;
        for (int i = 0; i < len; ++i) s += char('a' + rng() % letters);
        string r = reorganize(s);
        bool p = possibleFormula(s);
        possible += p;
        if (p ? !isValid(s, r) : !r.empty()) bad++;
    }
    cout << "random inputs: " << possible << " possible, " << bad << " wrong\n";
}

The program prints:

aab -> aba
aaabbc -> abacba
aaaabbbc -> ababacba
aaaaabbb -> (impossible)
random inputs: 192930 possible, 0 wrong

The random check uses one to five letters, with lengths up to 14. Every answer it returned had no equal neighbours and used the same letters as the input. Every input the formula called impossible returned an empty string.

Common mistakes

The first mistake is to put the letter back into the heap at once, with no hold. The method then forgets that the letter just placed must wait. Here is that broken version, which differs from the correct one only in where the pushback happens:

#include <array>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
using namespace std;
 
string naive(const string& s) {
    array<int, 26> freq{};
    for (char c : s) freq[c - 'a']++;
    priority_queue<pair<int, char>> heap;
    for (int i = 0; i < 26; ++i)
        if (freq[i] > 0) heap.push({freq[i], static_cast<char>('a' + i)});
    string out;
    while (!heap.empty()) {
        auto [copies, letter] = heap.top();
        heap.pop();
        out += letter;
        if (copies - 1 > 0) heap.push({copies - 1, letter});
    }
    return out;
}
 
int main() {
    cout << "aaab -> " << naive("aaab") << "\n";
}

It prints aaab -> aaba. The first two letters are both a, which breaks the rule. The fix is to keep the letter aside for one step, as the correct version does.

The second mistake is to skip the final check. The correct version ends with if (held.first > 0) return "";. Without that line, the method returns whatever it built, even when a letter is missing. For aaab, the method stops after placing aba and still holds one a. Deleting the check makes the function return aba for aaab.

The result is shorter than the input, so it is not a rearrangement. The fix is to keep the check, and return an empty string when a copy is left over.

The third mistake is to use the wrong rounding in the impossibility test. The correct limit is (n + 1) / 2. A common slip is to write n / 2, which is too small for odd lengths. For aaabb, which has length 5 and a with three copies, the correct test allows the answer, because (5 + 1) / 2 is 3. The wrong test rejects it. The program reorganize("aaabb") returns ababa, which is valid, so the wrong test would reject a case that has an answer.

The fourth mistake is to build the heap of letters without the counts. A heap of single letters puts the largest letter on top, which is alphabetical order, not the order by copies. Here is a program that makes this mistake:

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
 
int main() {
    priority_queue<pair<char, int>> heap;
    heap.push({'a', 3});
    heap.push({'b', 1});
    heap.push({'c', 2});
    while (!heap.empty()) {
        auto [ch, c] = heap.top();
        heap.pop();
        cout << ch << " " << c << "\n";
    }
}

It prints c 2, then b 1, then a 3. The pair starts with the letter, so the heap sorts by letter. The fix is to put the count first, as pair<int, char> does, so that the heap sorts by copies.

Practice

1. Run the program on aabb. Is the output one of the valid answers? Name another valid answer.

Show the answer

The program prints baba. The output has no equal neighbours and uses two a and two b, so it is valid. Another valid answer is abab. Any string with no equal neighbours and the same letter counts is correct.

2. Use the formula to decide whether aaaaabbb can be rearranged, and explain the answer.

Show the answer

No. The length is 8, so the limit is (8 + 1) / 2 = 4. The letter a has five copies, and 5 is greater than 4. Five copies of a need five positions that do not touch. In a string of length 8, the largest set of such positions is four, namely 1, 3, 5 and 7, so two a letters would have to touch.

3. Trace the method by hand on aab. What is held after the first step, and what goes into the output?

Show the answer

After the first step, the output is a, and the held letter is a with one copy left, written as the pair (1, 'a'). The heap now holds b with one copy. The second step places b and pushes the held a back, so the output is ab. The third step places a again, and the output is aba.

4. The answer for aaabb is ababa. Use the formula to show that an answer must exist, then explain why ababa is the only valid answer.

Show the answer

The length is 5, so the limit is (5 + 1) / 2 = 3. The letter a has three copies, and 3 is at most 3, so an answer exists. Three positions in a row of five that do not touch can only be 1, 3 and 5, so the three a letters must go there. That leaves positions 2 and 4 for the b letters, so the only valid string is ababa.

5. The naive program returns aaba for aaab. Change it so that it returns the right answer for every input, and say which line you changed.

Show the answer

Use the held pair from the correct version. Store the placed letter in held instead of pushing it right away, and push the old held letter before the next pick. The line that changes is the if (copies - 1 > 0) heap.push(...) line. Also add the final check that returns an empty string when the held letter still has copies.

Summary

• A valid arrangement has no two equal letters next to each other.
• At each step, place the letter with the most copies left, unless it is the letter just placed.
• Hold the placed letter for one step, so it cannot be picked again right away.
• A string is possible when the largest count is at most (n + 1) / 2, where n is its length.
• When the heap runs out and the held letter still has copies, no arrangement exists, so return an empty string.