Spread Letters at Least K Apart
Problem
Rearrange the letters of a string so that any two equal letters are at least k positions apart, meaning their indices differ by k or more. Among the letters allowed at each position, always place the one with the most copies left, taking the alphabetically smallest on a tie, so the answer is unique. If no arrangement exists, return an empty string. The string has up to 100,000 lowercase letters.
Examples
Input: s = "aabbcc", k = 3
Output: "abcabc"
Why: each letter waits for the other two before it can repeatInput: s = "aaadbbcc", k = 2
Output: "abacabcd"
Why: a has the most copies, so it goes first whenever its cooldown allowsInput: s = "aaabc", k = 3
Output: ""
Why: edge case, three a's need a span of 7 positions and only 5 existHints
0 / 3
Placing the letter with the most copies left first is the safe greedy choice: that letter is the one most likely to run out of room.
Keep the available letters in a heap of (-count, letter). A letter you just placed is not available again until k positions later.
Park each placed letter in a queue with the index at which it becomes free. Before each position, move the queue's front back into the heap if its time has come. If the heap is empty while letters are still waiting, the arrangement is impossible.
Solution
The greedy rule is to spend the most plentiful letter as early as it is allowed, because the letter with the most copies is the one that needs the most room; spending a rare letter first can only leave the common one stuck at the end. A heap of (-count, letter) gives that letter, with the alphabetical tie-break built into the tuple order. The cooldown is a plain FIFO queue: letters leave the heap when placed and come back once k positions have passed, and since they enter the queue in position order, only its front ever needs checking. If at some position the heap is empty but letters are still waiting, every remaining letter is on cooldown and no arrangement exists. With n letters and an alphabet of size a, time is O(n log a) and space is O(a).
import heapq
from collections import Counter, deque
def spread_letters(s, k):
heap = [(-n, ch) for ch, n in Counter(s).items()]
heapq.heapify(heap) # most copies left first, then alphabetical
waiting = deque() # (index it is free again, -count, letter)
out = []
while heap or waiting:
if waiting and waiting[0][0] <= len(out):
_, n, ch = waiting.popleft()
heapq.heappush(heap, (n, ch)) # its cooldown is over
if not heap:
return "" # everything left is still cooling down
n, ch = heapq.heappop(heap)
out.append(ch)
if n + 1:
waiting.append((len(out) - 1 + k, n + 1, ch))
return "".join(out)
print(spread_letters("aabbcc", 3)) # -> abcabc
print(spread_letters("aaadbbcc", 2)) # -> abacabcd
print(spread_letters("aaabc", 3)) # -> (empty string)Stuck on the idea rather than the code? Reorganize a String covers it.