Reorganize String — LeetCode 767 Greedy Max-Heap Interleaving

Problem Statement#

Given a string s, rearrange the characters so no two adjacent characters are the same. Return any valid rearrangement, or "" if impossible.

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters

Input:  s = "aab"
Output: "aba"

Input:  s = "aaab"
Output: ""

Why This Problem Matters#

LeetCode 767 Reorganize String is a flagship Amazon, Meta, and Google interview question. It teaches the greedy max-heap with cooldown pattern, which generalizes to Task Scheduler (LC 621) and Rearrange String K Distance Apart (LC 358).

The aha moment: at any step, pick the two most frequent characters that are not the last placed. This guarantees no repetition and uses up the highest-frequency characters first.

Keywords: "reorganize string interview", "FAANG greedy heap", "no two adjacent equal", "max heap cooldown".

The Core Insight#

Feasibility check: any character appearing more than (n + 1) / 2 times cannot be separated. Reject early.

Greedy: build a max-heap of (-count, char). Each step, pop the top, place it, decrement, then save aside until the next step. The "cooldown" of size 1 prevents adjacency.

Equivalently: pop top two, place both, decrement, push back if non-zero.

Visual Dry Run#

s = "aab". Counts: a=2, b=1.

s = "aaab". max count = 3, but (4 + 1) / 2 = 2. 3 > 2, impossible. Return "".

Solution (Optimal)#

import heapq
from collections import Counter
 
class Solution:
    def reorganizeString(self, s):
        cnt = Counter(s)
        if max(cnt.values()) > (len(s) + 1) // 2:
            return ""
        h = [(-c, ch) for ch, c in cnt.items()]
        heapq.heapify(h)
        out = []
        prev_c, prev_ch = 0, ""
        while h:
            c, ch = heapq.heappop(h)
            out.append(ch)
            if prev_c < 0:
                heapq.heappush(h, (prev_c, prev_ch))
            prev_c, prev_ch = c + 1, ch
        return "".join(out)

class MaxHeap {
    constructor(cmp) { this.h = []; this.cmp = cmp; }
    push(v) { this.h.push(v); this._up(this.h.length - 1); }
    pop() {
        const top = this.h[0], last = this.h.pop();
        if (this.h.length) { this.h[0] = last; this._down(0); }
        return top;
    }
    size() { return this.h.length; }
    _up(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.cmp(this.h[p], this.h[i]) >= 0) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    _down(i) {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = 2 * i + 2;
            let s = i;
            if (l < n && this.cmp(this.h[l], this.h[s]) > 0) s = l;
            if (r < n && this.cmp(this.h[r], this.h[s]) > 0) s = r;
            if (s === i) break;
            [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
            i = s;
        }
    }
}
 
var reorganizeString = function(s) {
    const cnt = new Map();
    for (const c of s) cnt.set(c, (cnt.get(c) || 0) + 1);
    let maxC = 0;
    for (const c of cnt.values()) maxC = Math.max(maxC, c);
    if (maxC > Math.floor((s.length + 1) / 2)) return "";
 
    const h = new MaxHeap((a, b) => a[0] - b[0]);
    for (const [ch, c] of cnt) h.push([c, ch]);
    let out = "", prev = null;
    while (h.size()) {
        const [c, ch] = h.pop();
        out += ch;
        if (prev && prev[0] > 0) h.push(prev);
        prev = [c - 1, ch];
    }
    return out;
};

Time: O(n log k) where k is alphabet size (constant 26). Effectively O(n). Space: O(k).

Common Mistakes#

• Skipping the feasibility check — heap will run, but final string has adjacent duplicates.
• Using > n // 2 instead of > (n + 1) // 2 — odd-length edge case.
• Forgetting to re-push the previous character after using it once.
• Mutating tuples in Python instead of pushing new ones.
• Off-by-one when decrementing: c + 1 for negative counts, c - 1 for positive.

Interview Tips#

• Begin with the feasibility check — it shows you understand the boundary.
• Mention the cooldown trick: pop, place, hold, then re-push next iteration.
• Two-pop variant is symmetric: pop two, place both, decrement, push back.
• For large alphabets, the heap is still O(n log k); essentially linear.

Follow-up Questions#

• What about K distance apart (LC 358)? Cooldown queue of size K - 1.
• What if multiple valid outputs are required? Stable tie-break by character.
• What if you must keep the original relative order where possible? Treat ties by index.
• Streaming variant? Buffer characters and emit when feasibility allows.

Key Takeaways#

• LeetCode 767 is solvable in O(n) average via max-heap with size-1 cooldown.
• Feasibility: max count must not exceed (n + 1) / 2.
• The greedy choice "always pick the most-frequent non-cooldown character" is optimal.
• Generalizes to Task Scheduler and Rearrange K Distance Apart.
• Two-pop variant is equivalent and slightly easier to write.
• Always check feasibility before running the heap.
• Watch the off-by-one when decrementing negated counts.