Hints — p45 Reorganize String

Hint 1. Feasibility FIRST. Answer exists iff max_count ≤ (N + 1) // 2. Pigeonhole: if any char has more than that, the “separators” between its occurrences run out. Compute Counter(s).values() and check before doing any work.

Hint 2. Greedy idea: always place the most-frequent remaining character (most constrained → handle first). But the naïve “pop, append, push back with count - 1” puts the SAME char right back at the top of the heap, causing adjacent duplicates.

Hint 3. The fix is one-iteration delay (stash). After popping char ch, don’t push it back yet. Stash it. On the NEXT iteration, pop a (necessarily different) char, append, and only THEN push the stashed ch back if it still has count > 0.

prev_count, prev_char = 0, ''
while heap:
    c, ch = heappop(heap)
    out.append(ch)
    if prev_count < 0: heappush(heap, (prev_count, prev_char))
    prev_count, prev_char = c + 1, ch

Hint 4. Alternative WITHOUT a heap: counting-sort placement. Sort chars by count desc; place them at indices 0, 2, 4, ... (even), wrapping to 1, 3, 5, ... (odd) when even slots fill. Feasibility check guarantees no collision (the highest-count char fits within the (n+1)//2 even slots).

chars = sorted(cnt.keys(), key=lambda c: -cnt[c])
out = [''] * n
idx = 0
for ch in chars:
    for _ in range(cnt[ch]):
        out[idx] = ch
        idx += 2
        if idx >= n: idx = 1

Hint 5. Generalization: K-distance (LC 358) — replace the one-slot stash with a queue of size K-1. Cooldown scheduler (LC 621) is the same shape with cooldown delay. The “delayed reinsertion” pattern is the reusable lesson.

If still stuck: see solution.py.