⚡Flashcard Drill➔
NeetCode #543LC-767MediumHeap / Priority QueueNC 250
← Back to All Problems

#543 · #767 · Reorganize String(重构字符串)

📌 Problem Statement & Constraints

Given a string s, rearrange its characters so that no two adjacent characters are the same. Return any valid arrangement, or the empty string if impossible. Constraints: 1 <= s.length <= 500, lowercase letters.

💡 Core Algorithmic Approaches

  1. The arrangement is possible exactly when no character occurs more than ceil(n / 2) times.
  2. A max-heap of (count, char) lets you always place the most frequent remaining character.
  3. After placing a character, hold it aside for one step so it cannot be placed immediately again.
  4. If the heap empties before the string is complete, the arrangement is impossible.

💻 Benchmark Python3 Implementation

class Solution:
    def reorganizeString(self, s: str) -> str:
        from collections import Counter
        import heapq
        cnt = Counter(s)
        h = [(-c, ch) for ch, c in cnt.items()]
        heapq.heapify(h)
        res = []
        held = None                        # the character placed in the previous step
        while h:
            c, ch = heapq.heappop(h)
            res.append(ch)
            c += 1                         # counts are negative
            if held:                       # release the held character
                heapq.heappush(h, held)
            held = (c, ch) if c < 0 else None
        if len(res) != len(s):
            return str()                   # impossible arrangement
        return "".join(res)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log k) where k is the number of distinct characters.
💾 Space Complexity
O(k) for the heap.

⚠️ Interview Pitfalls & Follow-ups

  • Pushing the just-used character back immediately: it could be popped again on the next step, creating an adjacent duplicate.
  • Forgetting the feasibility check: the final length comparison catches it.
  • Using a sorted list and scanning: O(n * k) instead of O(n log k).
  • Returning a partial result: the empty string is required when no valid arrangement exists.
⚡
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