Reorganize String: Greedy Max-Heap With a Held-Back Letter

Reorganize string asks you to rearrange the letters of a string so that no two neighbours are equal, or report that it cannot be done. It is a greedy problem wearing a heap, and the whole solution hangs on one small device: the letter you just placed is kept out of the heap for exactly one round. Get that device right and the code is ten lines. Explain why the greedy choice is safe and you have answered the real question.

The problem it solves

Given "aabbcc", return something like "abcabc". Given "aaab", return an empty string, because there are three as and only one other letter to separate them. Any valid arrangement is accepted.

Trying permutations is hopeless: a string of length n has up to n! of them. Two better ideas:

• Greedy with a max-heap. At each position, place the letter with the most copies left that is not the one you just placed. O(n log k) for k distinct letters.
• Counting and slot filling. Put the commonest letter on the even indices first, then pour the rest into the remaining even slots and the odd ones. O(n + k), no heap at all.

Both depend on the same feasibility rule, and it is worth saying first.

The intuition

When is it possible? A letter that appears m times needs at least m - 1 other letters to sit between its copies, so m can be at most (n + 1) // 2: every other slot, starting at the first. If the commonest letter fits under that bound, an arrangement always exists; if it does not, none does.

Why pick the commonest remaining letter? Because it is the one at risk. If you spend the rare letters first, the frequent one piles up at the end with nothing left to separate its copies. Spending the largest count first keeps the counts as even as possible, and even counts are easy to interleave.

Why hold the letter back? The heap always offers its top, and right after you place a, the top may still be a. Removing it from the heap for one round makes that choice impossible. After the next letter is placed, a is legal again, so it goes back in with its count reduced by one. If the heap is ever empty while letters are still held back, the only letter left is the one you just placed, and the arrangement has failed.

Watch it run

The animation uses the lesson's string: six letters, two of each. No two neighbours may match, so the commonest remaining letter always goes next. Place a; it is now held back so it cannot be picked twice in a row. Place b, then let a back into the heap, since it has had its one round out. Place c, and let b back in. Place a again, and let c back in. Then b, then c, until the output reads abcabc, with no two neighbours alike. Had one letter outnumbered the rest, the heap would have emptied early.

The code

The lesson's heap version. Python's heapq is a min-heap, so counts are stored negated, and the held entry carries its already reduced count:

import heapq
from collections import Counter

def reorganize(s):
    heap = [(-n, ch) for ch, n in Counter(s).items()]
    heapq.heapify(heap)                      # commonest letter on top
    out, held = [], None
    while heap:
        n, ch = heapq.heappop(heap)          # never the letter placed last round
        out.append(ch)
        if held:
            heapq.heappush(heap, held)       # that one is legal again now
        held = (n + 1, ch) if n + 1 else None
    return "".join(out) if len(out) == len(s) else ""

print(reorganize("aabbcc"))    # abcabc
print(reorganize("aaabbc"))    # ababac
print(repr(reorganize("aaab")))   # ''   'a' would fill 3 of 4 slots

The half-length rule, which lets you answer "is it possible?" before doing any work:

def possible(s):
    return not s or max(Counter(s).values()) <= (len(s) + 1) // 2

print(possible("aab"), possible("aaab"), possible("aaabb"))   # True False True

The heap-free version fills even indices first, starting with the commonest letter, then wraps round to the odd ones. Because the commonest letter goes first and fits in the even slots, no letter can ever land next to itself:

def reorganize_slots(s):
    if not possible(s):
        return ""
    counts = Counter(s)
    order = sorted(counts, key=lambda ch: -counts[ch])   # commonest first
    out, i = [None] * len(s), 0
    for ch in order:
        for _ in range(counts[ch]):
            if i >= len(s):
                i = 1                        # evens full: continue on the odds
            out[i] = ch
            i += 2
    return "".join(out)

print(reorganize_slots("aaabbc"))   # ababac
print(repr(reorganize_slots("aaab")))   # ''

Both against brute force on 3,000 random short strings, where the brute force tries every permutation:

from itertools import permutations
import random

def valid(s, t):
    return sorted(s) == sorted(t) and all(a != b for a, b in zip(t, t[1:]))

def brute_exists(s):
    return any(valid(s, "".join(p)) for p in set(permutations(s)))

random.seed(20)
ok = True
for _ in range(3000):
    s = "".join(random.choice("aabbc") for _ in range(random.randint(0, 7)))
    exists = brute_exists(s)
    ok &= possible(s) == exists
    for t in (reorganize(s), reorganize_slots(s)):
        ok &= valid(s, t) if exists else t == ""
print(ok)                           # True

The complexity

• Heap version: O(n log k) time for n letters and k distinct ones, since each placement is one pop and at most one push on a heap of at most k entries. O(k) extra space.
• Slot version: O(n + k log k) for the count and the sort by frequency, which is O(n) when the alphabet is fixed at 26 letters.
• With a fixed alphabet, k is at most 26, so both are linear in practice.

Where it goes wrong

• Pushing the held letter back before popping. Then it can be popped straight away and placed twice in a row. Pop first, then return the held letter.
• Holding a letter with no copies left. A count of zero must be dropped, not held, or it comes back as a phantom letter.
• Checking len(out) == len(s) and forgetting why. The heap empties early exactly when the only letter left is the one being held.
• Getting the bound wrong. It is (n + 1) // 2, not n // 2: "aba" is fine with two as in three slots.
• In the slot version, not starting with the commonest letter. Filling evens with a rare letter first can leave the frequent one straddling the even-to-odd wrap.

When it shows up in interviews

It is a regular medium question on heaps and greedy choice, and a close cousin of task scheduler with cooldown, where the held-back pen becomes a queue with a clock. Interviewers probe the feasibility bound, the reason the commonest letter must go first, and whether you can drop the heap. The generalisation, keeping equal letters at least k apart, is the same held-back idea with a queue of k entries instead of one. For choosing between a heap and sorting in general, see top-k elements.

How to say it in an interview

"First, feasibility: the commonest letter can fill at most every other slot, so if its count exceeds half the length rounded up, I return an empty string. Otherwise I use a max-heap of counts. Each round I pop the letter with the most copies left and append it, then push back the letter I held from the previous round, and hold the current one with its count reduced, so it cannot be chosen twice in a row. Spending the largest count first stops it from piling up at the end. That is O(n log k). With a fixed alphabet I can also skip the heap: place the commonest letter on even indices, then fill the remaining slots, in linear time."