Rearrange String k Distance Apart
Rearrange a string so identical characters are at least k positions apart using a max-heap and a cooldown queue.
Rearrange String k Distance Apart
Problem: Given a string s and an integer k, rearrange s so that the same characters are at least k positions apart. Return any valid arrangement, or an empty string if impossible.
Example:
- Input:
s = "aabbcc",k = 3 - Output:
"abcabc"— each character is at least 3 apart from its duplicate - Input:
s = "aaabc",k = 3→ Output:""— impossible
Note
This is a generalization of Reorganize String (LC 767), where k = 2. The key addition: after placing a character, it must "cool down" for k-1 positions before it can be used again. A queue tracks this cooldown window.
How to Think About It
Starting point: This is Reorganize String (no two adjacent identical) generalized to k distance apart. The same greedy logic applies: always place the most frequent character that's currently available.
What changes with k? "Available" now means the character wasn't placed in any of the last k-1 positions. After placing a character, it must sit out for k-1 steps before it can be used again.
Modeling the cooldown: Use a queue alongside the max-heap. After placing a character, push it (with its remaining count) into the queue. The queue represents characters in cooldown. After each step, if the queue's front has waited k-1 steps, release it back into the heap.
How to know when to release: The queue always holds exactly the characters placed in the last k-1 positions. When the queue reaches size k, pop its front — that character has cooled down and can be used again.
Detecting impossibility: If the heap is empty but the cooldown queue still has characters, you can't fill the current position. Return "".
The pattern: Greedy + max-heap + cooldown queue. The queue manages the "blackout window" that prevents reuse within k positions.
Brute Force
View Brute Force
Optimal — Max-Heap + Cooldown Queue
View Optimal Solution
| Approach | Time | Space |
|---|---|---|
| Backtracking | O(n!) | O(n) |
| Max-Heap + Cooldown Queue | O(n log k) | O(n) |