NeetCode #530LC-358HardHeap / Priority QueueNC Algo100
← Back to All Problems#530 · #358 · Rearrange String k Distance Apart(K 距离间隔重排字符串)
📌 Problem Statement & Constraints
Given a string
s and an integer k, rearrange it so that the same characters are at least k positions apart. Return any valid arrangement, or the empty string if impossible. Constraints: 1 <= s.length <= 3 * 10^4, 0 <= k <= s.length, lowercase letters.💡 Core Algorithmic Approaches
- Process the string in blocks of size
k: within a block, place thekmost frequent characters. - A max-heap of
(count, char)supplies the most frequent characters for each block. - If a block cannot be filled completely and characters remain, the arrangement is impossible.
- Within a block, no character repeats, so the spacing constraint is satisfied by construction.
💻 Benchmark Python3 Implementation
class Solution:
def rearrangeString(self, s: str, k: int) -> str:
from collections import Counter
import heapq
if k <= 1:
return s # no spacing constraint
cnt = Counter(s)
h = [(-c, ch) for ch, c in cnt.items()]
heapq.heapify(h)
res = []
while h:
block = []
popped = 0
for _ in range(k):
if not h:
break
c, ch = heapq.heappop(h)
popped += 1
res.append(ch)
c += 1 # counts are negative
if c < 0:
block.append((c, ch))
# a partial block with deferred characters left over is impossible
if popped < k and block:
return ""
for item in block:
heapq.heappush(h, item)
return "".join(res)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log m) where m is the number of distinct characters.
💾 Space Complexity
O(m) for the heap.
⚠️ Interview Pitfalls & Follow-ups
- Returning a partial string when impossible: the empty string is required.
- Forgetting the
popped < k and blockcheck: the algorithm would loop, placing the same deferred characters adjacent to themselves. - Releasing deferred characters too early: they must wait until the next block.
- Using a queue with explicit cooldown timestamps: also correct, but the block formulation is shorter and easier to verify.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.