Reorganize String (LeetCode 767)
You're given a string s. Reorder its characters so that no two characters sitting next to each other are the same.
Return any ordering that satisfies this, or return an empty string "" if no such ordering exists.
Worked Examples
s = "aab""aba"b between the two as keeps equal letters apart.s = "aaab"""as need at least two other letters to separate them, but there is only one b, so no arrangement works.⚖️Formal Constraints & Bounds
1 <= s.length <= 500sconsists of lowercase English letters.
Core Insight
Greedily consuming highest-frequency characters with a 1-step buffer guarantees conflict-free interleaving.
Real-World Scenario & Production Applications
Task round-robin interleaving, distributed cluster resource anti-affinity scheduling.
Subproblems & Recurrence Decomposition3 Phases
Count every character's frequency and push (-count, char) for each into a max-heap (negated for Python's min-heap). If any character's count exceeds ceil(len(s) / 2), no valid rearrangement exists.
freq = Counter(s)
if max(freq.values()) > (len(s) + 1) // 2:
return ""
heap = [(-count, ch) for ch, count in freq.items()]
heapify(heap)Step-by-Step Execution Trace Table
| Step | Heap State (Freq, Char) | Chosen Char | Buffered Previous | Result String |
|---|---|---|---|---|
| 1 | [(2, 'a'), (1, 'b')] | 'a' | (1, 'a') | 'a' |
| 2 | [(1, 'b')] | 'b' | Re-push 'a' | 'ab' |
| 3 | [(1, 'a')] | 'a' | None | 'aba' |
| 1 | counts = Counter(s) |
| 2 | max_heap = [(-cnt, ch) for ch, cnt in counts.items()] |
| 3 | heapify(max_heap) |
| 4 | prev_cnt, prev_ch = 0, '' |
| 5 | result = [] |
| 6 | while max_heap: |
| 7 | cnt, ch = heappop(max_heap) |
| 8 | result.append(ch) |
| 9 | if prev_cnt < 0: |
| 10 | heappush(max_heap, (prev_cnt, prev_ch)) |
| 11 | prev_cnt, prev_ch = cnt + 1, ch |
| 12 | res_str = ''.join(result) |
| 13 | return res_str if len(res_str) == len(s) else '' |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Arranging characters so that no two adjacent characters are identical is a greedy scheduling problem. If any character's frequency exceeds $\lceil N/2 \rceil$, the Pigeonhole Principle proves an arrangement is impossible. Otherwise, we greedily place the character with the highest remaining frequency, holding it in a temporary cooldown buffer for one step so it cannot be placed next to itself, then re-enqueuing it into the max-heap. 🎪 The Analogy: Seating Departments So No Two From the Same Team Sit Together
Imagine seating people from several departments in a row so no two people from the same department ever sit next to each other. Greedily seat someone from whichever department currently has the most people left unseated — that department is the most "constrained," so give it priority now, while you still have the most flexibility. But immediately after seating them, put that department on a one-seat cooldown: it cannot be selected again until one more person (from a different department) has been seated first.
🔑 The Key Idea in the Code
Holding the just-used character out of the heap for exactly one iteration — instead of pushing it straight back — is the entire "cooldown" mechanism, implemented with zero extra data structures beyond the heap itself.
Impossible arrangement condition: If any character has frequency , pigeonhole principle proves adjacent identical characters cannot be avoided; return
''immediately.Pushing previously used character back into heap immediately: Re-inserting the character into the max-heap before popping the next character causes the same character to be chosen twice in a row. Hold it in a temporary variable and only push it back on the next iteration.
Character count parity on odd string lengths: For odd , the most frequent character can appear at most times and must occupy the even indices (0, 2, 4, ...).
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Rearranging characters/tasks to prevent adjacent identical elements.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: most frequent remaining character is always prioritized.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Pigeonhole violation: if max frequency > (len(s) + 1) // 2, valid rearrangement is impossible.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Most Frequent First. I count the characters and put them in a max-heap by count, stored negated because Python's heap is a min-heap. Each step I pop the character with the most copies left and append it. The character I placed last waits in a one-slot holding buffer and only goes back into the heap after the next character is placed, so the same character can never land twice in a row. Placing the biggest pile first keeps it from being stranded at the end. The trap is pushing the held character back before popping the next one: I would just pick it again. If the heap runs empty while a character still waits, the result is shorter than s and I return an empty string. That is O(N log A) time and O(A) space for an alphabet of size A."
Complexity & Mathematical Proof
O(N log A)
Counting reads all N characters once: O(N). The loop then runs once per character of s (at most N times). Each pass does one heappop and at most one heappush (the held character going back), on a heap of at most A entries, so each pass is O(log A). Joining result is O(N). Total O(N log A), which is O(N) for the 26 lowercase letters of this problem.
O(A)
counts and max_heap hold one entry per distinct character, O(A). The holding buffer prev_cnt, prev_ch is O(1). No recursion. The output string itself is O(N) and is not counted as auxiliary space.
T(N) = O(N) + N · O(log A) = O(N log A)
Derivation Progression
Counter(s) ⟹ O(N)
Reads every character once; heapify of at most A pairs is O(A).
≤ N loop passes × O(log A)
Each pass pops the most frequent allowed character and pushes back at most the held one.
O(N)
"".join(result) and the length test that detects a stuck arrangement.
Variable Definitions
Length of the input string
Alphabet size: distinct characters in s (at most 26 lowercase English letters here)
Memory Architecture & Bounds
O(1) Iterative
O(A) counts and max-heap, plus the O(1) holding buffer
O(N) Reorganized string (not counted as auxiliary)
Boundary Best / Worst Cases
: the count always reads the whole string; an impossible input only stops the heap loop early.
.
for a valid arrangement.
Binary Heap Priority Queue Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "reorganize string so that no two adjacent characters are the same", "return empty string if not possible". Equal items must be kept apart and the biggest pile is the hardest to place, so a Most Frequent First max-heap with a one-slot holding buffer builds the answer.
, lowercase English letters only, so . Time budget , which is here.
The failure test is at the end (len(res_str) == len(s)), so a stuck input still reads the whole string once to count it.
Core Algorithmic State Invariants
- The Heap Is Sized by the Alphabet
max_heap holds one (-count, char) pair per distinct character, never one per position. With lowercase letters that is at most 26 entries, so each pop or push is effectively constant; with a large alphabet of A distinct values, each costs O(log A).
Reorganize String (LeetCode 767)
You're given a string s. Reorder its characters so that no two characters sitting next to each other are the same.
Return any ordering that satisfies this, or return an empty string "" if no such ordering exists.
Worked Examples
s = "aab""aba"b between the two as keeps equal letters apart.s = "aaab"""as need at least two other letters to separate them, but there is only one b, so no arrangement works.⚖️Formal Constraints & Bounds
1 <= s.length <= 500sconsists of lowercase English letters.
Core Insight
Greedily consuming highest-frequency characters with a 1-step buffer guarantees conflict-free interleaving.
Real-World Scenario & Production Applications
Task round-robin interleaving, distributed cluster resource anti-affinity scheduling.
Subproblems & Recurrence Decomposition3 Phases
Count every character's frequency and push (-count, char) for each into a max-heap (negated for Python's min-heap). If any character's count exceeds ceil(len(s) / 2), no valid rearrangement exists.
freq = Counter(s)
if max(freq.values()) > (len(s) + 1) // 2:
return ""
heap = [(-count, ch) for ch, count in freq.items()]
heapify(heap)Step-by-Step Execution Trace Table
| Step | Heap State (Freq, Char) | Chosen Char | Buffered Previous | Result String |
|---|---|---|---|---|
| 1 | [(2, 'a'), (1, 'b')] | 'a' | (1, 'a') | 'a' |
| 2 | [(1, 'b')] | 'b' | Re-push 'a' | 'ab' |
| 3 | [(1, 'a')] | 'a' | None | 'aba' |
| 1 | counts = Counter(s) |
| 2 | max_heap = [(-cnt, ch) for ch, cnt in counts.items()] |
| 3 | heapify(max_heap) |
| 4 | prev_cnt, prev_ch = 0, '' |
| 5 | result = [] |
| 6 | while max_heap: |
| 7 | cnt, ch = heappop(max_heap) |
| 8 | result.append(ch) |
| 9 | if prev_cnt < 0: |
| 10 | heappush(max_heap, (prev_cnt, prev_ch)) |
| 11 | prev_cnt, prev_ch = cnt + 1, ch |
| 12 | res_str = ''.join(result) |
| 13 | return res_str if len(res_str) == len(s) else '' |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Arranging characters so that no two adjacent characters are identical is a greedy scheduling problem. If any character's frequency exceeds $\lceil N/2 \rceil$, the Pigeonhole Principle proves an arrangement is impossible. Otherwise, we greedily place the character with the highest remaining frequency, holding it in a temporary cooldown buffer for one step so it cannot be placed next to itself, then re-enqueuing it into the max-heap. 🎪 The Analogy: Seating Departments So No Two From the Same Team Sit Together
Imagine seating people from several departments in a row so no two people from the same department ever sit next to each other. Greedily seat someone from whichever department currently has the most people left unseated — that department is the most "constrained," so give it priority now, while you still have the most flexibility. But immediately after seating them, put that department on a one-seat cooldown: it cannot be selected again until one more person (from a different department) has been seated first.
🔑 The Key Idea in the Code
Holding the just-used character out of the heap for exactly one iteration — instead of pushing it straight back — is the entire "cooldown" mechanism, implemented with zero extra data structures beyond the heap itself.
Impossible arrangement condition: If any character has frequency , pigeonhole principle proves adjacent identical characters cannot be avoided; return
''immediately.Pushing previously used character back into heap immediately: Re-inserting the character into the max-heap before popping the next character causes the same character to be chosen twice in a row. Hold it in a temporary variable and only push it back on the next iteration.
Character count parity on odd string lengths: For odd , the most frequent character can appear at most times and must occupy the even indices (0, 2, 4, ...).
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Rearranging characters/tasks to prevent adjacent identical elements.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: most frequent remaining character is always prioritized.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Pigeonhole violation: if max frequency > (len(s) + 1) // 2, valid rearrangement is impossible.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Most Frequent First. I count the characters and put them in a max-heap by count, stored negated because Python's heap is a min-heap. Each step I pop the character with the most copies left and append it. The character I placed last waits in a one-slot holding buffer and only goes back into the heap after the next character is placed, so the same character can never land twice in a row. Placing the biggest pile first keeps it from being stranded at the end. The trap is pushing the held character back before popping the next one: I would just pick it again. If the heap runs empty while a character still waits, the result is shorter than s and I return an empty string. That is O(N log A) time and O(A) space for an alphabet of size A."
Complexity & Mathematical Proof
O(N log A)
Counting reads all N characters once: O(N). The loop then runs once per character of s (at most N times). Each pass does one heappop and at most one heappush (the held character going back), on a heap of at most A entries, so each pass is O(log A). Joining result is O(N). Total O(N log A), which is O(N) for the 26 lowercase letters of this problem.
O(A)
counts and max_heap hold one entry per distinct character, O(A). The holding buffer prev_cnt, prev_ch is O(1). No recursion. The output string itself is O(N) and is not counted as auxiliary space.
T(N) = O(N) + N · O(log A) = O(N log A)
Derivation Progression
Counter(s) ⟹ O(N)
Reads every character once; heapify of at most A pairs is O(A).
≤ N loop passes × O(log A)
Each pass pops the most frequent allowed character and pushes back at most the held one.
O(N)
"".join(result) and the length test that detects a stuck arrangement.
Variable Definitions
Length of the input string
Alphabet size: distinct characters in s (at most 26 lowercase English letters here)
Memory Architecture & Bounds
O(1) Iterative
O(A) counts and max-heap, plus the O(1) holding buffer
O(N) Reorganized string (not counted as auxiliary)
Boundary Best / Worst Cases
: the count always reads the whole string; an impossible input only stops the heap loop early.
.
for a valid arrangement.
Binary Heap Priority Queue Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "reorganize string so that no two adjacent characters are the same", "return empty string if not possible". Equal items must be kept apart and the biggest pile is the hardest to place, so a Most Frequent First max-heap with a one-slot holding buffer builds the answer.
, lowercase English letters only, so . Time budget , which is here.
The failure test is at the end (len(res_str) == len(s)), so a stuck input still reads the whole string once to count it.
Core Algorithmic State Invariants
- The Heap Is Sized by the Alphabet
max_heap holds one (-count, char) pair per distinct character, never one per position. With lowercase letters that is at most 26 entries, so each pop or push is effectively constant; with a large alphabet of A distinct values, each costs O(log A).