Rearrange String k Distance Apart

Rearrange String k Distance Apart is a classic greedy-plus-heap problem. The trick that makes it click: at every position, place the character you have the most of — but enforce a cooldown so no character repeats within a window of k.

The slow way first

You might try to build the answer by brute force: try every permutation and check the spacing rule. That is O(n! · n) — hopelessly slow even for short strings. Backtracking with pruning is better but can still blow up when many characters are scarce.

The question to ask: which character should go next? If you ever delay placing a high-frequency character, you can get stuck later with too many copies and nowhere to put them. So the greedy instinct is right: always place the most frequent character you are still allowed to use.

The idea: most frequent first, then cool it down

Keep a max-heap keyed by remaining count. Each round, pop the most frequent character, append it to the result, and decrement its count. Then push that character into a cooldown queue. Only once the queue holds k items do we pop its front and, if that character still has copies left, return it to the heap. That single rule guarantees a placed character cannot reappear until k positions have passed.

If the heap ever empties while a character with copies left is still stuck in cooldown, no valid arrangement exists, so we return "".

Walk through it

Step through the animation with s = "aabbc", k = 3. The output cells fill left to right. The heap line shows remaining counts; the cooldown line shows who is waiting. Watch how a is placed first, sits in cooldown for three rounds, and only then becomes eligible again — producing "abcab".

Pseudocode

if k <= 1: return s                       # no spacing required
count every character
max-heap of (count, char)
result = []; cooldown = empty queue
while heap is not empty:
    pop (count, char) with the largest count
    append char to result
    push (count - 1, char) onto cooldown
    if cooldown has k items:
        (cnt, ch) = pop front of cooldown
        if cnt still > 0: push (cnt, ch) back to heap
return result if it used every char, else ""

The Python solution

def rearrange(s, k):
    if k <= 1:
        return s
    heap = [(-c, ch) for ch, c in Counter(s).items()]
    heapify(heap)
    res, cooldown = [], deque()
    while heap:
        c, ch = heapq.heappop(heap)
        res.append(ch)
        cooldown.append((c + 1, ch))
        if len(cooldown) >= k:
            cnt, char = cooldown.popleft()
            if cnt < 0:
                heapq.heappush(heap, (cnt, char))
    return "".join(res) if len(res) == len(s) else ""

• Python only has a min-heap, so we store negative counts to simulate a max-heap. (-c, ch) makes the most frequent char pop first.
• c, ch = heapq.heappop(heap) pulls the heaviest remaining character. c is negative, so c + 1 actually decrements its true count.
• We append (c + 1, ch) to cooldown immediately, even if its count is now zero.
• The if len(cooldown) >= k block is the cooldown release: once k items are waiting, the front has spent k rounds, so it is eligible again.
• if cnt < 0 means the released char still has copies left (remember counts are negative), so we push it back to the heap.
• At the end, if res did not consume every character, some char was trapped in cooldown with copies left, so we return "".

Complexity

With n the string length and A the number of distinct characters, the heap holds at most A entries, so each push/pop is O(log A). Total time is O(n log A), and since A is bounded by the alphabet this is effectively linear.

When this pattern shows up

Practice