⚡Flashcard Drill➔
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

  1. Process the string in blocks of size k: within a block, place the k most frequent characters.
  2. A max-heap of (count, char) supplies the most frequent characters for each block.
  3. If a block cannot be filled completely and characters remain, the arrangement is impossible.
  4. 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 block check: 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.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems