Hints — p87 Reorganize String
-
Feasibility check first:
max_freq <= (n + 1) // 2(pigeonhole). If violated, return"". -
Heap approach: max-heap of (-count, char). Place top; buffer it for one turn so it can’t be picked again immediately. Next turn, pop a different letter, then push the buffered one back.
-
Even-index approach: sort letters by frequency descending. Fill positions 0, 2, 4, … with copies of the most frequent letter; continue with next-most-frequent; wrap to odd positions when even positions exhausted.
-
Both achieve O(n log k) or O(n + k log k). Even-index is simpler; heap generalizes to k-distance (LC 358).
-
Validation: every adjacent pair must differ; total counts must match input.
If stuck: see solution.py.