A fulfillment desk prints badge codes and serial stickers. Adjacent cells cannot share a letter — the scanner reads a doubled glyph as a smudge and the tote goes to the wrong bay. The intern version sorted each code and glued identical letters into one run. A dozen unique letters looked fine. A burst of one letter with a thin mix of others still printed as a smear.

Reorganize String asks you to rearrange so no two adjacent characters are the same, or return empty if that is impossible. A heap already gives the next-loudest remaining count at the root. Trying rearrangements uses that answer and still pays a tree of placements.

This is an interview writeup, not a heap lecture. That post owns sift. Java’s PriorityQueue is a min-heap. Invert it so poll is the largest remaining count. Task Scheduler is the same greedy heap with a cooldown of 1, except that problem may idle. This string cannot: if the only leftover is the letter you just placed, fail. Last Stone Weight already extracts a max; this post holds the previous letter off the heap for one turn.

The problem

Given a string s of lowercase letters, rearrange the characters so no two adjacent characters are the same. Return any valid rearrangement, or an empty string if none exists.

s = "lllmn"  →  "lmlnl"
s = "ppqrs"  →  "pqprs"
s = "qqqr"   →  ""
s = "wxyz"   →  "wxyz"

First row: three ls and two singles. Alternate the loud letter so no two ls touch. Second: two ps, the rest unique — any valid interleave. Third: three qs in a string of length 4; after q r q the leftover q has nowhere to sit. Fourth: every letter is unique, so the string is already valid.

Note: Any legal rearrangement is an accepted answer. Do not chase a lexicographically smallest string unless they ask.

Trying rearrangements is the honest brute force

The intern glue-the-runs sort is wrong even when a rearrangement exists — "lllmn" stays a smear. The honest brute tries placements. Backtracking builds the string one letter at a time, skips the last character, and returns the first full string with no adjacent pair the same. Correct. Exponential in the leftover counts.

String reorganizeBacktrack(String s) {
    int[] freq = new int[26];
    for (char c : s.toCharArray()) {
        freq[c - 'a']++;
    }
    StringBuilder sb = new StringBuilder();
    return place(freq, sb, s.length(), -1) ? sb.toString() : "";
}

boolean place(int[] freq, StringBuilder sb, int n, int last) {
    if (sb.length() == n) {
        return true;
    }
    for (int i = 0; i < 26; i++) {
        if (freq[i] == 0 || i == last) {
            continue;
        }
        freq[i]--;
        sb.append((char) ('a' + i));
        if (place(freq, sb, n, i)) {
            return true;
        }
        sb.deleteCharAt(sb.length() - 1);
        freq[i]++;
    }
    return false;
}

At a short badge this is a rounding error. At a long serial with one hot letter the search tree is still huge for a question a heap answers with one poll: which letter has the most remaining that is not the one you just placed?

Max-heap of remaining counts, hold the previous

Count once. Offer every positive {count, letter} into a max-heap. PriorityQueue is a min-heap; compare b[0] against a[0] so the root is the loudest leftover. Say the invert out loud.

Cooldown of 1 is just prev. No ArrayDeque. Poll the loudest, append it, decrement, then offer the previous leftover back if it still has count. The letter you just placed sits aside until the next turn, so it cannot sit next to itself.

  • While the heap is nonempty, poll, append, decrement.
  • Offer prev back only after that append, and only if its count is still positive.
  • Then prev = cur.
  • If the builder length is not s.length(), a leftover never found a partner letter — return "".

You never permute. You never idle. Empty heap with leftover in prev is failure.

s = "lllmn"
count: l→3  m→1  n→1
max-heap of [count, letter]: [3,l] [1,m] [1,n]

poll l  append l  hold [2,l]               heap [1,m] [1,n]
poll m  append m  offer [2,l]  hold [0,m]  heap [2,l] [1,n]
poll l  append l  hold [1,l]               heap [1,n]
poll n  append n  offer [1,l]  hold [0,n]  heap [1,l]
poll l  append l  hold [0,l]               heap empty
→ "lmlnl"

s = "qqqr"
count: q→3  r→1

poll q  append q  hold [2,q]               heap [1,r]
poll r  append r  offer [2,q]  hold [0,r]  heap [2,q]
poll q  append q  hold [1,q]               heap empty
leftover still in hold; length 3 ≠ 4
→ ""

The Java is that walk. Optional early-out: if any count is greater than (n + 1) / 2, return "" before the heap. The greedy fails the same way on "qqqr" without it.

String reorganizeString(String s) {
    int[] freq = new int[26];
    for (char c : s.toCharArray()) {
        freq[c - 'a']++;
    }
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) {
            heap.offer(new int[] { freq[i], 'a' + i });
        }
    }
    StringBuilder sb = new StringBuilder();
    int[] prev = null;
    while (!heap.isEmpty()) {
        int[] cur = heap.poll();
        sb.append((char) cur[1]);
        cur[0]--;
        if (prev != null && prev[0] > 0) {
            heap.offer(prev);
        }
        prev = cur;
    }
    if (sb.length() != s.length()) {
        return "";
    }
    return sb.toString();
}

Time is O(n log U) — n placements, U distinct letters (at most 26). Each step is one poll and maybe one offer. Space is O(U) for the heap. Do not re-lecture sift at the whiteboard unless they ask.

Note: Offer prev back only after you have placed a different letter. Offer it first and the loudest leftover is often the one you just wrote, so you print a doubled glyph. A natural-order PriorityQueue polls the rarest letter first and burns the singles that should have sat between the hot letter’s copies.

What interviewers usually poke next

  • Impossible bound. If the max count is greater than (n + 1) / 2, two copies of that letter must sit together in any layout of length n. "qqqr" is 3 against 2. The heap’s length check catches it; the bound is the follow-up.
  • All unique letters. Return s (or any permutation). The hold never blocks; every poll is a new letter.
  • Task Scheduler vs this. Same most-frequent-first heap. There, cooldown n may idle and the answer is a duration. Here, cooldown is 1 and idle is not a slot you can insert — leftover of the letter you just placed is "", not a longer string.
  • Even/odd slots. Place the hottest letter at indices 0, 2, 4, … then fill the rest. If that letter does not fit the even slots, fail. An array trick, not the board default when they said heap.
  • Why most-frequent-first. The hottest letter writes the skeleton. Other letters sit in the gaps. Spend the rares first and those gaps have nothing left to sit in.
  • One letter only. "zzzz" is already adjacent copies. Length-1 "z" is already valid. The while loop places it once and the length check passes.

You are done with this problem when you can say, out loud, why trying rearrangements is correct, why a reversed PriorityQueue plus a one-slot hold peeks the next-loudest letter that is not the one you just placed, and why idle here is failure rather than a longer schedule.