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.

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)`

LeetCode 358 — Rearrange String k Distance Apart