Pop-k-then-rebuild (frequency greedy)

46 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Rearrange the letters of "aaabbc" so that no two equal letters are next to each other. By hand you would spread out the most common letter first: a _ a _ a _, then fill the gaps with b, b, c: a b a b a c. The rule that worked was "place the letter you have the most of, as early as you can, but never right after itself".

Trying arrangements at random is hopeless: 6 letters have 60 distinct arrangements, 20 letters have billions. And a simple greedy of "take letters in alphabetical order" gives a a a b b c, wrong at once. The ordering must be by remaining count, and the count changes after every placement.

Build the structure, one piece at a time

Piece one: count each letter. a: 3, b: 2, c: 1. A frequency table.

Piece two: a max-heap keyed by remaining count, holding (count, letter). Its top is always the letter with the most copies still to place.

Piece three: a cooldown slot. After you write a letter, it is not allowed in the very next position, so instead of pushing it back into the heap at once, hold it aside for one turn. On the next turn, first pop and write the new top, then return the held letter to the heap (if it still has copies left) and hold the one you just wrote.

If at some turn the heap is empty but a letter is still held, no valid arrangement exists: that letter has nowhere to go but next to itself. For a cooldown of k turns instead of one, the "held aside" slot becomes a queue of length k.

Why it is correct

The invariant: the heap holds every letter that still has copies and is allowed at the next position; the held slot holds the one letter that is temporarily forbidden. Each turn writes a letter from the heap, so adjacent equal letters never happen by construction.

Why does always taking the most frequent letter succeed whenever any arrangement exists? The danger is one letter with too many copies left relative to the remaining positions. Writing the most frequent letter first reduces the largest count as early as possible, which keeps the remaining counts as even as possible. If the most frequent letter x has count f and the string has length n, an arrangement exists exactly when

f ≤ ⌈n / 2⌉

and the greedy never violates this for the remaining string, because it only ever lowers the maximum count when the maximum is what it writes, and otherwise the maximum was already within bound for a shorter remainder.

Why it is fast

Each of the n positions does one pop and at most one push on a heap of at most 26 letters (one per distinct letter): O(n log 26), which is effectively O(n). Counting is O(n) too. The random-arrangement search was factorial; the greedy is linear.

How to recognise it in an interview

"No two equal letters adjacent", "same tasks must be at least k apart", "schedule by frequency with a cooldown". Say: "I will keep a max-heap by remaining count and a cooldown queue, always placing the most frequent available item." Reorganize String is this with a one-turn cooldown. Task Scheduler is the same with a cooldown of n turns and idle slots when the heap runs empty before the cooldown expires; it also has a closed-form answer, (max count − 1) × (n + 1) + number of letters tied for the maximum, floored by the total length. Rearrange String k Distance Apart generalises the queue to length k.

02The idea in one line

Always schedule the most frequent remaining item that is not on cooldown.

Reach for it when: Task scheduler, reorganise string, rearrange string k distance apart.

Cost: O(n log k) time.

03The walk-through, step by step

The video works one example: Reorganize String 'aaabbc'. These are its captions in order, so you can follow without the video or check a step you missed.

1. Count letters: a×3, b×2, c×1; the most frequent goes first
2. Pop the most frequent, a (3 left), write it
3. Pop the most frequent, b (2 left), write it
4. Now a may come back: it is no longer adjacent to the output
5. Pop the most frequent, a (2 left), write it
6. Now b may come back: it is no longer adjacent to the output
7. Pop the most frequent, b (1 left), write it
8. Now a may come back: it is no longer adjacent to the output
9. Pop the most frequent, a (1 left), write it
10. Pop the most frequent, c (1 left), write it
11. Result ababac: every letter waited one turn before returning
12. n pops and pushes on a heap of ≤ 26 letters: O(n log 26)

04Asked at Google

5 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Heap: Top-k with a size-k heap, Two heaps (running median), K-way merge, Greedy scheduling with a heap, Lazy deletion heap.