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
- The arrangement is possible exactly when no character occurs more than
ceil(n / 2)times. - A max-heap of
(count, char)lets you always place the most frequent remaining character. - After placing a character, hold it aside for one step so it cannot be placed immediately again.
- 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.