Reorganize String: Adjacent Duplicates and Greedy Pairing

If you interview at Amazon, Google, Pinterest, expect some version of "Reorganize String". It is rated Medium, and it falls squarely into the Top-K and Heaps pattern — pattern-first preparation beats grinding random problems every time. Part 8 of 11 in the Top-K and Heaps arc.

The Problem

Rearrange a string so no two adjacent characters are equal, or return an empty string if impossible. Task Scheduler's sibling: cooldown of exactly one, but you must produce the arrangement, so the arithmetic shortcut no longer suffices on its own.

Input:  s = "aab"
Output: "aba"
For "aaab" the answer is "" — impossible.

Recognizing the Top-K and Heaps Pattern

When a problem asks for the k largest, smallest, closest, or most frequent — or for repeated access to an extreme while data changes — a heap gives O(log n) insertion and O(1) access to the extreme. The signature trick: keep a bounded heap of size k with the opposite polarity (a min-heap to track the k largest), evicting the root on overflow. Python's heapq is a min-heap; negate values for max behavior.

Spacing duplicates apart is the greedy: always place the most frequent remaining letter that is not the one just placed — two heap pops per step (take the top, hold it out, take the second). Feasibility has a clean precondition — no letter may exceed half the length rounded up — checkable before any work.

The Approach

Check max_count <= (len(s) + 1) // 2; fail fast otherwise. Then max-heap by count: pop the most frequent, append it, hold it aside (cooldown of one), pop the next, append, decrement and re-push both as counts allow. The hold-out slot is the cooldown queue at n = 1.

The alternative O(n) construction — fill even indices with the most frequent letter, then odd indices with the rest — is elegant and worth naming, but the heap version generalizes to k-apart spacing and that is the follow-up.

Python Solution

import heapq
from collections import Counter


def reorganize_string(s: str) -> str:
    """Rearrangement with no equal neighbors, or '' if impossible."""
    counts = Counter(s)
    if max(counts.values()) > (len(s) + 1) // 2:
        return ""
    heap = [(-count, ch) for ch, count in counts.items()]
    heapq.heapify(heap)

    pieces: list[str] = []
    prev_count, prev_ch = 0, ""
    while heap:
        count, ch = heapq.heappop(heap)
        pieces.append(ch)
        if prev_count < 0:
            heapq.heappush(heap, (prev_count, prev_ch))
        prev_count, prev_ch = count + 1, ch      # one copy used
    return "".join(pieces)

Complexity

• Time: O(n log d) — n placements, heap over d distinct letters
• Space: O(d) — counts and heap over the alphabet

Interview Tips and Follow-Ups

• Derive the feasibility bound rather than asserting it: the most frequent letter needs a gap after each copy except the last. Derivations beat memory.
• Generalization k-apart (Rearrange String k Distance Apart) swaps the single hold-out for a cooldown queue of size k − 1 — exactly Task Scheduler's machinery.
• Verify output with the neighbor-check loop in your own tests, not by eyeballing — multiple valid outputs exist and string equality tests overfit.

More Top-K and Heaps problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.