p87 — Reorganize String

Source: LeetCode 767 · Medium · Topics: Heap, Greedy, Counting Companies (2024–2025): Amazon (high), Meta (medium), Google (medium), TikTok (medium) Loop position: Pigeonhole feasibility + max-heap with cooldown buffer. Tests whether you derive the tight feasibility condition before coding.

1. Quick Context

Rearrange string s so no two adjacent chars are equal. Return any valid rearrangement, or "" if impossible.

Feasibility: Possible iff max_freq ≤ (n + 1) // 2. Proof: if some letter appears > (n+1)/2 times, by pigeonhole two of them must be adjacent (only ≤ (n-1)/2 + 1 = (n+1)/2 slots non-adjacent).

Construction (max-heap + 1-step cooldown):

• Push (-count, char) for each letter.
• Pop top; append char; decrement count; buffer it (don’t push back yet).
• On next iteration, pop top (different letter, guaranteed because buffered letter was the most frequent), append; push the buffered one back if count > 0; buffer current.

Alternative: place into even indices first (0, 2, 4, …) then odd indices, starting with the most frequent letter.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/reorganize-string/

STOP. 30-min timer. Derive the feasibility condition before coding.

3. Prerequisite Concepts

• Max-heap via negation in Python’s heapq.
• collections.Counter.
• Pigeonhole reasoning.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Rearrange so no two adjacent chars are equal.

2. Clarify: Lowercase only? Usually yes. Empty string?

3. Examples: "aab" → "aba". "aaab" → "".

5. Brute: Permute n! and check.

6. Target: O(n log k) where k = distinct letters ≤ 26.

7. Pattern: Max-heap with cooldown buffer.

8. Develop: see solution.py.

9. Test: all distinct; majority letter; exact feasibility threshold; n=1.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 The pigeonhole feasibility bound — tight

Letters must occupy alternating slots. n positions can hold at most ⌈n/2⌉ = (n+1)//2 copies of any one letter (positions 0, 2, 4, …). If max_freq > (n+1)//2, infeasible.

6.2 Why the cooldown buffer works

After placing letter L, never pick L again until we’ve placed at least one other letter. The heap holds all available letters; the buffered letter is unavailable for this turn. After the next placement, push buffer back.

Correctness: as long as feasibility holds, at every turn there exists ≥ 2 distinct letters with count > 0 or exactly one letter left with count = 1. In the first case the heap has ≥ 2 entries and we pick the freshest; in the second case the buffer is empty.

6.3 Even-index construction — simpler proof

Sort letters by frequency descending. Fill positions 0, 2, 4, ... with copies of the most frequent letter; continue with next-most-frequent. After filling all even positions, fill 1, 3, 5, ....

Why it works: the most frequent letter goes to even positions only — no two of it are adjacent. Other letters’ counts are smaller, so they can’t form adjacency either (by pigeonhole on smaller frequency).

6.4 Comparison: heap vs even-index

• Heap: more flexible (handles weighted variants, k-distance generalization LC 358).
• Even-index: simpler, O(n + k log k).
• Production: even-index for this exact problem; heap for the k-distance generalization.

6.5 Generalization: LC 358 Rearrange String k Distance Apart

Same problem but require ≥ k distance between same letters. Cooldown buffer becomes a queue of size k (FIFO); push back into heap after k turns.

6.6 Family: cooldown / spacing problems

• LC 767 Reorganize String (this; k=2).
• LC 358 Rearrange String k Distance Apart (general k).
• LC 621 Task Scheduler (cooldown by time, not adjacency).
• LC 1054 Distant Barcodes (same as 767).

7. Anti-Pattern Analysis

1. Use min-heap by frequency — places sparsest letters first; fails on aab.
2. Forget the feasibility check — heap algorithm “succeeds” but produces an invalid string.
3. Push buffered letter back too early — adjacent placements of same letter.
4. Greedy without proof — works but unconvincing.
5. Sort string and zip with itself — only works in very narrow cases.
6. Use Counter.most_common() once — counts change as you place; must reuse heap.

8. Skills & Takeaways

• Pigeonhole-derived feasibility.
• Max-heap with explicit cooldown buffer.
• Even-index construction as an alternative.

9. When to Move On

• Solve cold in 20 min using either approach.
• Derive max_freq ≤ (n+1)//2.
• Cite k-distance generalization.

10. Company Context

• Amazon: L5; common screen.
• Meta: E5; heap pattern signal.
• Google: L5; pigeonhole derivation expected.
• TikTok: mid; standard heap-greedy.

Strong: “Heap with cooldown buffer OR even-index construction; pigeonhole feasibility max_freq ≤ (n+1)//2 derived; cited LC 358 k-distance generalization.”

11. Interviewer’s Lens

12. Level Delta

• Mid (L4): Heap greedy buggy on cooldown; corrects with hint.
• Senior (L5): Both heap and even-index; feasibility derivation.
• Staff (L6): + generalizes to k-distance (LC 358).
• Principal (L7+): + framing as chromatic number of distance-1 conflict path graph + LP relaxation for k-distance + connection to broadcast scheduling.

13. Follow-up Q&A

Q1: Return lexicographically smallest valid string? A1: Heap by (count desc, char asc) breaks pure correctness; the standard greedy doesn’t give lex-smallest. Use DP over (position, last_char, remaining_counts) or backtracking.

Q2: k-distance apart (LC 358)? A2: Cooldown queue size k. Each placement, pop oldest from cooldown (push back to heap if count > 0), then pop heap top.

Q3: Streaming letters arrive online; output as they arrive? A3: Maintain heap; emit whenever the heap top differs from the last emitted char. May need to buffer.

Q4: Multiple constraints (no adjacent + balanced subsequence)? A4: DP over state; typically NP-hard for arbitrary regex-like constraints.

Q5: What if counts include weights (a different letter is “twice as bad”)? A5: Weighted greedy; max-heap by weight × count.

14. Solution Walkthrough

See solution.py:

• reorganize_string_heap — max-heap with cooldown buffer.
• reorganize_string_even_index — fill even then odd indices.
• reorganize_string_brute — permutation oracle.

15. Beyond the Problem

Principal code review: “Reorganize String is the smallest version of a broadcast / interleaving scheduling problem that appears in WiFi MAC layer design (avoid same-station back-to-back transmissions), CPU branch prediction (avoid same-target speculation chains), and audio/video frame interleaving (avoid temporal clustering of same-codec frames). The Staff+ recognition: the pigeonhole bound max_freq ≤ ⌈n/2⌉ generalizes to any periodic schedule with period k: feasibility becomes max_freq ≤ ⌈n/k⌉. This is the load-bound in scheduling theory — a hard combinatorial constraint that no algorithm can violate. The interesting follow-up is when some letters can be relaxed (low-priority interleaved with high-priority) and the bound becomes a weighted load with LP duality. The lesson: whenever you face a ‘no two X adjacent’ problem, your first move is to compute the pigeonhole bound and check feasibility. If infeasible, the problem is unsolvable; if feasible, a constructive algorithm exists — heap, even-index, or for harder variants, LP rounding.”