Rearrange String k Distance Apart

Intuition

To keep identical characters far apart, we should always spend the character that has the most copies left, because it is the hardest one to place later. A max-heap keyed on remaining count gives us that character in logarithmic time. After emitting a character we cannot reuse it until k positions have passed, so we park it in a cooldown queue; only when the queue grows to length k does the front element become eligible to re-enter the heap. If the heap ever empties while characters are still waiting in cooldown, we could not place everyone with the required spacing, so the arrangement is impossible.

Algorithm walkthrough

1. 1If k is 0 or 1 there is no spacing constraint, so return s unchanged.
2. 2Count character frequencies and push each (count, character) pair into a max-heap.
3. 3Pop the character with the largest remaining count, append it to the result, and decrement its count.
4. 4Push the just-used character into a cooldown queue holding the last k picks.
5. 5Once the queue reaches size k, remove its front element and, if it still has copies left, push it back onto the heap.
6. 6When the heap is empty, return the result if it covers every character, otherwise return an empty string.

Implementation

import heapq
from collections import Counter, deque

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        if k <= 1:
            return s
        counts = Counter(s)
        heap = [(-cnt, ch) for ch, cnt in counts.items()]
        heapq.heapify(heap)
        result = []
        queue = deque()
        while heap:
            cnt, ch = heapq.heappop(heap)
            result.append(ch)
            queue.append((cnt + 1, ch))
            if len(queue) < k:
                continue
            front_cnt, front_ch = queue.popleft()
            if front_cnt < 0:
                heapq.heappush(heap, (front_cnt, front_ch))
        return "".join(result) if len(result) == len(s) else ""