Reorganise a string with a max heap in Python

Why it matters

Suppose you have a list of letters and you want to lay them out so that no two equal letters touch. A seating plan at a dinner works this way. Two people from the same family should not sit side by side. A playlist works this way too. You do not want the same artist back to back. Each case has a simple question: can every item be placed so that its neighbours differ?

The question has a clear greedy answer, and it uses a heap. Greedy means making the best choice at each step, using only what is known at that step. The letter that appears most often is the hardest to separate, so it should go down first. A max heap, which always gives back the largest item first, finds that letter quickly. You meet the heap idea in the first lesson of this module. This lesson uses heapq, the standard library module for heaps, as a max heap.

The same idea also settles when an answer does not exist. If one letter is too frequent, no arrangement can keep it apart from itself. The lesson shows two ways to detect that, and why they agree.

The problem in plain words

You are given a string, such as aab. Its letters are a, a, and b. The task is to reorder them so that no two equal letters are next to each other. One answer is aba. The two a letters sit at the ends, with the b between them.

Some strings have no answer. Take aaab. The letter a appears three times, and there is only one other letter to separate them. The three a letters need at least two separators between them, and only one b is available. So the answer is impossible.

The output of the task is a new string with the same letters, or a signal that no such string exists. In Python, the usual signal is None. None is a built-in value that means "nothing here". The code returns None when the answer is impossible. The function signature says so: -> str | None means the function returns either a string or None. Python does not enforce this note at run time, but editors and type checkers read it.

The key idea: place the most frequent letter first

Count how many times each letter appears. Call that number the count of the letter. The letter with the largest count is the one most likely to get stuck. Placing it early, while many other letters are still free, gives it the most room. A tie means two letters have the same count.

The greedy plan is:

1. Build a max heap of letters, ordered by count. The top of the heap is the letter with the most copies left.
2. Take the top letter. If it is different from the last letter written, write it and reduce its count.
3. If the top letter equals the last letter written, it cannot go next. Take the next letter from the heap, write it instead, and reduce its count. Then put the blocked letter back into the heap, unchanged.
4. If that blocked letter is the only one left, the answer is impossible.
5. Keep going until the heap is empty.

Step 3 is the trick. A letter that cannot go next is not thrown away. It waits in the heap, and a different letter gets written in its place. Then the blocked letter is free to go on the following step.

heapq only makes min heaps, which give back the smallest item first. To get the largest count first, the code stores each count as a negative number. The count 3 becomes -3, and -3 is the smallest value, so it comes out first. Each entry is a pair (-count, letter). When two counts are equal, Python compares the letters, so ties are broken in alphabetical order every time you run the code.

Take aab as an example. The counts are a = 2 and b = 1.

At step 2 the heap holds a1 and b1. Both have count 1, so the tie is broken by the letter, and a comes out first. It clashes with the last letter, which is also a. So the code takes b instead, writes it, and puts a1 back into the heap. Step 3 then writes a. The result is aba.

Why the most frequent letter is the risk

A letter with c copies needs at least c - 1 other letters, one between each pair of copies. The shortest string that holds c copies of one letter, with no two touching, is c copies plus c - 1 separators. Its length is 2c - 1.

In a string of length L, the most copies one letter can have is therefore the largest c with 2c - 1 <= L. That gives c <= (L + 1) / 2. In Python, the // operator does whole-number division, so (L + 1) // 2 drops any fraction. The code uses // for that reason.

Here is the check in plain numbers:

• aaab has length 4. The most copies allowed is (4 + 1) // 2 = 2. The letter a has 3 copies, which is too many. The answer is impossible.
• aaabb has length 5. The most copies allowed is (5 + 1) // 2 = 3. The letter a has 3 copies, which is allowed. The answer exists.
• aaaabbb has length 7. The most copies allowed is (7 + 1) // 2 = 4. The letter a has 4 copies, which is allowed.

The check uses only the largest count, and it does not depend on the other letters. That makes it a very fast test. The heap method gives the same yes or no answer, and it also builds the string.

Two ways to detect the impossible case

The lesson uses two detection methods, and they agree.

The first is the formula above. Count the letters, find the largest count, and compare it with (length + 1) // 2. If the count is too large, return impossible. This test runs before any building.

The second is the heap itself. When the top letter clashes with the last letter written, and the heap has no other letter to take, the code has no valid move. It returns None. This detection happens during the build, so the code never needs the formula at all.

A separate check ran both methods on all 9,840 strings of length 1 to 8 made from the letters a, b, and c. It found no disagreement. Every string the heap method solved was a valid arrangement with the same letters.

The Python code

This module holds the heap method, the formula, and a show function that prints results for several inputs. Python runs the code under if __name__ == "__main__": only when you run the file directly, not when another file imports it.

A few details in the code matter.

Counter(s) counts each character in the string. It works for any characters, not only the letters a to z.

The heap is a plain list of tuples. heapq.heapify(heap) arranges the list into heap order in one pass. Each tuple is compared by its first item, then by its second item if the first items are equal. This is why the letter breaks ties.

Python tuples cannot be changed. So the code makes a new tuple each time a count goes down, and it pushes that new tuple onto the heap.

Python strings cannot be changed in place. The code collects the letters in the list out and joins them with "".join(out) at the end.

The check out[-1] != ch looks only at the last letter written. That is enough, because the rule is only about neighbours. If out is empty, the not out part is true, so the first letter is always written.

The blocked letter goes back as the same tuple it came from, (neg, ch). Its count does not change, because no copy of it was written.

To run the file, save it as reorganise.py and use these commands:

python3 reorganise.py

The output below was made with Python 3.14.4:

aab -> "aba" formula=True
aaab -> impossible formula=False
aaabb -> "ababa" formula=True
aabbcc -> "abcabc" formula=True
aaabbbcc -> "ababcabc" formula=True
vvvlo -> "vlvov" formula=True
aaaaab -> impossible formula=False
abbbbbcc -> impossible formula=False

Python prints True and False with capital letters. Every line where the formula says True has a valid string. Every line where it says False is impossible. The string for vvvlo is vlvov. The letters l and o each have count 1, so their order is a tie, and the letter order decides it. A different tie-break rule could give another valid string, such as vovlv. Any valid string counts as a correct answer.

Worked example 1: aab

The first example is the one traced above. Its output is aba. The key point is that the code does not need the formula. The heap alone keeps the a letters apart. Read the table again, and notice that the blocked letter goes back into the heap with the same count. Nothing is lost.

Worked example 2: aaabb

The counts are a = 3 and b = 2. The formula says the answer exists, because 3 <= (5 + 1) // 2.

Here is the trace with the tie-break by letter:

The most frequent letter goes at the ends of the string, and the other letter fills the gaps. Here a takes positions 1, 3, and 5, and b takes positions 2 and 4.

Worked example 3: aaabbbcc

The counts are a = 3, b = 3, and c = 2. The length is 8, so the most copies allowed are (8 + 1) // 2 = 4. Every letter fits.

The program prints ababcabc. Read it left to right and check each neighbour. a and b alternate at the start. The last four places hold c, a, b, and c. Count the letters: a appears 3 times, b appears 3 times, and c appears 2 times.

This example is harder than the first two, because three letters compete for space. The letters with the highest counts are the ones placed first. The heap keeps the counts in order at every step.

Common mistakes

Dropping the blocked letter

The most common bug is to forget to put the blocked letter back. Here is the same program with the line heapq.heappush(heap, (neg, ch)) removed from the clash branch. The blocked letter is then lost from the heap, and the output is shorter than the input.

aab -> "ab" formula=True
aaab -> "ab" formula=False
aaabb -> impossible formula=True
aabbcc -> "abcabc" formula=True
aaabbbcc -> "ababcabc" formula=True
vvvlo -> "vlo" formula=True
aaaaab -> "ab" formula=False
abbbbbcc -> "bcac" formula=False

The line for vvvlo shows the problem. The input has five letters, but the output has three. Two of the three v letters are missing from the output. A quick check catches this: the output length must equal the input length, and the letter counts must match. Add that check to any test you write.

Using a result without checking for None

reorganise returns None for an impossible input. Using that value as a string fails at once. The code below uses the result without checking it first:

from reorganise import reorganise
 
print(len(reorganise("aaab")))

When this runs, Python stops and prints the last line of the error. The lines above it show the file and line number:

TypeError: object of type 'NoneType' has no len()

Calling a string method on the result fails in a similar way, with AttributeError: 'NoneType' object has no attribute 'upper'. The fix is to check the result before using it: if result is None:. The show function does this with text = f'"{result}"' if result is not None else "impossible".

Taking the least frequent letter first

Some people try to place the rare letters first. That needs the heap to return the smallest count first, which means the tuples store the count without a minus sign. Here is the same program with every minus sign removed, so each entry is (count, letter). The first two lines of its output are:

aab -> impossible formula=True
aaabb -> impossible formula=True

The input aab has a valid answer, aba, but this version reports it as impossible. The heap gives b first, which writes b. Then a is written, and the next a clashes with the a just before it. Nothing else is left in the heap, so the method gives up. Placing the most frequent letter first is what avoids this.

Forgetting the length

The formula uses the length of the string, not the number of distinct letters. For aaabb, there are two distinct letters. Using that number gives (2 + 1) // 2 = 1. The count 3 would then look too large, and the method would wrongly report impossible. The length 5 gives (5 + 1) // 2 = 3, which is correct. Always compare with len(s).

Practice

Exercise 1

Is it possible to reorder aaabbc so that no two neighbours are equal? If yes, write one valid string.

Show the answer

Yes. The length is 6, and the largest count is 3 for a. The formula gives (6 + 1) // 2 = 3, and 3 <= 3, so the answer exists. The program returns ababac. Check the neighbours: a and b, b and a, a and b, b and a, and a and c. None of them are equal.

Exercise 2

Is it possible to reorder aaaabb? Explain your answer in plain words.

Show the answer

No. The length is 6, and the letter a has 4 copies. The formula gives (6 + 1) // 2 = 3, and 4 is larger than 3. In plain words, four a letters need three gaps between them, and there are only two b letters to fill gaps. The program returns None.

Exercise 3

Is it possible to reorder aaaabbb? If yes, write the string.

Show the answer

Yes. The length is 7, and (7 + 1) // 2 = 4. The letter a has 4 copies, which fits exactly. The only valid string is abababa, because every a must sit in one of the four odd positions with a b between each pair. The program returns that string.

Exercise 4

The code puts a blocked letter back into the heap with the same count. Explain why the count must stay the same, and what would go wrong if the code reduced it.

Show the answer

The blocked letter was not written, so it still has all of its copies left. Reducing its count would mean the code had written a copy that does not exist, and the output would be missing that letter. The count only goes down when a copy is actually written to the output.

Exercise 5

Using the least-frequent-first version from the mistakes section, trace the input aab. Write the result of each step, and say why the method reports impossible.

Show the answer

Step 1: the heap holds (1, "b") and (2, "a"). The smallest tuple is (1, "b"), so the method takes b and writes it. The output is b, and b is gone from the heap. Step 2: the heap holds (2, "a"). The method takes a, which does not clash with b, and writes it. The output is ba. The count of a drops to 1, and the tuple (1, "a") goes back into the heap. Step 3: the heap holds (1, "a"). The method takes a, but the last letter written is a, so it clashes. The heap is now empty, so the method returns None. The string aba exists, but the order of the heap cut off that path.

Summary

• A max heap keyed by letter count always gives the most frequent letter first, which is the hardest letter to separate.
• With heapq, store the negated count so that the largest count comes out first.
• A blocked letter waits in the heap, and another letter is written in its place. Its count changes only when a copy is written.
• A letter with c copies needs length 2c - 1 at least, so the test is max count <= (length + 1) // 2.
• Both the formula and the heap method detect impossible strings. The heap method also returns the string when it exists.
• Check any output by comparing its length and letter counts with the input, and by confirming that no two neighbours match.