Reorganize String (LeetCode 767)

The problem

You get a string s of lowercase letters. Rearrange its letters so that no two adjacent characters are the same, and return any such arrangement. If it’s impossible, return "".

Input:  "aab"     Output: "aba"
Input:  "aaab"    Output: ""

In "aaab" there are three a’s and only one other letter to separate them. Any arrangement puts two a’s side by side.

How to think about it

Start with brute force. Try permutations until one has no equal neighbours. That’s O(n!) and hopeless. A smarter thought: the danger is always the most frequent letter. If any letter appears more than (n + 1) / 2 times, it’s impossible; otherwise it’s always possible. The question is how to build the string.

The key insight: always place the letter with the most copies left, as long as it isn’t the one you just placed. Using up the most common letter early stops it piling up at the end, where it would have nothing to separate it. A max-heap of counts gives you “most remaining” in O(log k), where k is the number of distinct letters.

The hold-back trick. After you place a letter, don’t put it back in the heap straight away. Keep it aside as prev for exactly one step. On the next step you pop a different letter, and only then push prev back. That alone guarantees no letter is placed twice in a row. If the heap runs dry while a letter is still held back with copies left, you’re stuck, and the result comes out shorter than s. That is how the code detects “impossible”.

Which pattern is this? Heap-driven greedy. The tell is “rearrange so equal items are apart”: it’s Task Scheduler with a cooldown of 1, where you have to produce the actual sequence.

Approach

1. Count the letters. Push (-count, letter) for each onto a heap (negated, so it acts as a max-heap).
2. Pop the letter with the most copies left and append it to the result.
3. If the previously held letter still has copies, push it back now.
4. Hold the current letter as prev, with its count reduced by one.
5. Repeat until the heap is empty.
6. If the result is as long as s, return it; otherwise return "".

Solution

import heapq
from collections import Counter
def reorganize_string(s):
    cnt = Counter(s); h = [(-v, c) for c, v in cnt.items()]; heapq.heapify(h)   # max-heap by count
    res = []; prev = None
    while h:
        v, c = heapq.heappop(h); res.append(c)               # most copies left, and not the last letter
        if prev and prev[0] < 0: heapq.heappush(h, prev)     # last letter is allowed back now
        prev = (v + 1, c)                                    # hold this one back for a step (one copy used)
    out = "".join(res)
    return out if len(out) == len(s) else ""                 # someone got stuck: impossible
# reorganize_string("aab") -> "aba" ; reorganize_string("aaab") -> ""

Counts are stored negated, so v + 1 means “one copy used”, and prev[0] < 0 means “copies still left”.

Dry run

On "aab", starting with heap [(-2, 'a'), (-1, 'b')]:

The heap is empty and the result has length 3, so the answer is “aba”.

On "aaab" the same steps give "aba" with prev = (-1, 'a') still holding one a, but the heap is empty. Length 3 ≠ 4, so it returns "".

Complexity

• Time: O(n log k), where k is the number of distinct letters (at most 26). Each of the n placements does a pop and maybe a push.
• Space: O(k) for the heap and counter, plus O(n) for the output.

Edge cases and pitfalls

• Single character "a" returns "a".
• Impossible inputs return ""; the length check catches them without a separate count test.
• Pushing the letter back immediately is the classic bug: the heap hands the same letter straight back and you get "aa…".
• Quick feasibility test: if the top count is greater than (len(s) + 1) // 2, you can return "" straight away.
• Heap tuple order. Ties in count are broken by the letter; that’s fine, since any valid arrangement is accepted.

Related problems

• Task Scheduler (LeetCode 621): the general cooldown version, where only the length matters.
• Sort Characters By Frequency (LeetCode 451): the same counts, grouped together instead of spread out.
• Last Stone Weight (LeetCode 1046): a simpler max-heap simulation to warm up on.