Reorganize String LeetCode 767 Guide

LeetCode 767 Reorganize String asks you to rearrange a given string so that no two adjacent characters are the same. If any valid rearrangement exists, return it; otherwise return an empty string.

The key insight is that the most frequent character dominates the problem. If one character appears so often that it cannot be interleaved with the rest, no solution exists. For any other frequency distribution, a valid arrangement can always be constructed greedily.

The classic example is "aab" which becomes "aba" — the character "a" appears twice and "b" once, so we interleave them by always placing the most frequent available character first, ensuring no two "a" characters end up next to each other.

Before building the heap, check whether any character appears more than (n+1)/2 times, where n is the length of the string. If so, return an empty string immediately — it is impossible to place that character without repetition.

This follows from the pigeonhole principle applied to interleaving. In a string of length n, the most slots any single character can occupy without being adjacent to itself is ceil(n/2) = (n+1)//2. For "aaa" (n=3), that limit is 2, but "a" appears 3 times — impossible. For "aaab" (n=4), the limit is 2, but "a" appears 3 times — still impossible.

This early check saves heap construction time for inputs that are provably unsolvable, and it also simplifies the main loop: if we pass the check, we are guaranteed to build a complete valid string without ever running out of characters mid-way.

Count the frequency of each character and push all (frequency, character) pairs into a max-heap. In Python this means negating frequencies since heapq is a min-heap. Each iteration pops the most frequent remaining character, appends it to the result, and decrements its count.

The critical rule is the "hold": after popping character A and appending it, do not push it back to the heap immediately. Instead, hold it aside. On the next iteration, pop a different character B, append B, then push A back if its remaining count is still greater than zero.

This one-step delay guarantees that A is never placed in two consecutive positions. By the time A is re-inserted into the heap, at least one other character B has been placed between the previous A and the next A, satisfying the no-adjacent constraint.

The hold technique is the heart of this algorithm. After placing character A, we must ensure the very next character placed is not A. If we pushed A back onto the heap immediately after decrementing its count, and A still has the highest frequency, the heap would pop A again — creating "AA" in the result.

By holding A for exactly one step, we force the heap to serve up a different character B next. Only after B is placed do we re-insert A, making the result "...AB..." rather than "...AA...". The hold acts like a queue of size 1 that rotates characters through a mandatory gap.

This also explains why the algorithm terminates correctly: the heap shrinks by one unit of work each iteration (one character appended), and the hold never blocks progress as long as the frequency check passed. When the heap is exhausted after all holds are resolved, the result is complete.

Consider "aaab": frequencies are {a:3, b:1}, n=4, (n+1)/2=2. Max frequency is 3 which exceeds 2 — the impossibility check catches this immediately and returns "". No heap is ever built.

Now consider "aabb": frequencies are {a:2, b:2}, n=4, (n+1)/2=2. Max frequency is 2 which equals the limit — valid. Heap: [(-2,a), (-2,b)]. Pop (-2,a): result="a", hold=(-1,a). Pop (-2,b): push hold (-1,a) back, result="ab", hold=(-1,b). Pop (-1,a): push hold (-1,b) back, result="aba", hold=(0,a). Pop (-1,b): hold (0,a) has count 0 so skip push, result="abab", hold=(0,b). Heap empty — done.

The final result "abab" is one valid answer (note: "baba" is also valid — multiple arrangements may exist and any one is acceptable). The algorithm always produces exactly one deterministic answer based on the heap ordering.

In Python: from collections import Counter; import heapq. Count = Counter(s). heap = [(-freq, char) for char, freq in count.items()]; heapq.heapify(heap). result = []. prev = None. While heap: freq, char = heapq.heappop(heap); result.append(char); if prev and prev[0] < 0: heapq.heappush(heap, prev); prev = (freq + 1, char). Return "".join(result).

In Java: int[] freq = new int[26]; for (char c : s.toCharArray()) freq[c-"a"]++. PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> b[0]-a[0]). for (int i=0; i<26; i++) if (freq[i]>0) pq.offer(new int[]{freq[i], i}). StringBuilder sb = new StringBuilder(); int[] prev = null. While (!pq.isEmpty()): int[] curr = pq.poll(); sb.append((char)(curr[1]+97)); if (prev != null && prev[0] > 0) pq.offer(prev); prev = new int[]{curr[0]-1, curr[1]}. Return sb.toString().

Time complexity is O(n log 26) = O(n) because the heap never grows beyond 26 entries (one per lowercase letter). Space complexity is O(26) = O(1) for the heap and frequency array, plus O(n) for the output string.

Task Scheduler (LeetCode 621) is the direct sibling: instead of rearranging characters, you schedule CPU tasks with cooldown periods between same-task executions. The max-heap greedy and the hold/cooldown mechanism are nearly identical — both problems reduce to interleaving the most frequent item with gaps.

Minimum Deletions to Make Character Frequencies Unique (LeetCode 1647) asks how many characters to delete so all frequencies are distinct. It uses frequency counting and greedy reduction rather than a heap, but shares the same frequency-first thinking about what makes a string arrangement valid.

The broader family of greedy frequency placement problems includes Rearrange String k Distance Apart (LeetCode 358) — a generalization where the gap must be at least k instead of 1 — and Hand of Straights (LeetCode 846), which uses a greedy min-heap approach to form consecutive groups. Mastering Reorganize String unlocks all of these variants.