Reorganize String (No Two Adjacent Same)

Reorganize String asks you to rearrange a string so that no two adjacent characters are the same. It is the classic showcase for a greedy choice backed by a max-heap: at every step, do the most "urgent" thing — place the letter you have the most of left.

The slow way first

You could try every permutation of the string and check each one for adjacent duplicates. That is O(n! · n) — hopelessly slow for anything but the tiniest input. Backtracking is better but still explores many dead ends.

The question to ask: which letter is hardest to place? The one with the most copies remaining. If we keep deferring it, we may run out of safe slots. So a sensible rule emerges: always place the most frequent remaining letter first.

The idea: greedily place the most frequent letter

Count every letter. Then repeatedly pull out the letter with the highest remaining count and append it to the answer — with one catch: we must not place the letter we just placed. We handle that by holding back the previous letter for exactly one round, then returning it to the pool. A max-heap keyed by count gives us the most frequent letter in O(log k) each round.

There is also a quick feasibility check: if any letter appears more than (n + 1) // 2 times, the slots simply cannot hold it apart, so we return "" immediately.

Walk through it

Step through the animation with s = "aab" (counts a:2, b:1). We pop a and write it, holding a back. Next round b is the heaviest available, so we write b and return the held a to the heap. Finally a comes back and fills the last slot. The b sitting between the two a's guarantees they never touch, giving "aba".

Pseudocode

count each character
if the most common character appears more than (n + 1) // 2 times:
    return ""                          # impossible to separate
build a max-heap of (count, char)
prev = none                            # the char held back from last round
result = empty list
while the heap is not empty:
    take (count, char) with the highest count
    append char to result
    if prev exists:
        push prev back into the heap   # it has cooled down one round
    if char still has copies left:
        prev = (count - 1, char)       # hold this char back next
    else:
        prev = none
return result joined into a string

The Python solution

import heapq
from collections import Counter
def reorganize(s):
    counts = Counter(s)
    if max(counts.values()) > (len(s) + 1) // 2:
        return ""
    heap = [(-c, ch) for ch, c in counts.items()]
    heapq.heapify(heap)
    res, prev = [], None
    while heap:
        c, ch = heapq.heappop(heap)
        res.append(ch)
        if prev:
            heapq.heappush(heap, prev)
        prev = (c + 1, ch) if c + 1 < 0 else None
    return "".join(res)

• Counter(s) tallies how many of each letter we have.
• The feasibility line returns "" early when one letter is too common to separate.
• We store counts as negatives (-c) so Python's min-heap behaves like a max-heap — the most frequent letter pops first.
• Each round we pop the heaviest letter and append it, then push back prev (the letter parked last round) so it is available again.
• prev = (c + 1, ch) if c + 1 < 0 keeps the just-placed letter parked only if it still has copies left (remember c is negative, so c + 1 < 0 means count remained positive).

Complexity

With at most k distinct letters (26 for lowercase English), the heap is tiny, so the work is dominated by the n rounds, each an O(log k) heap operation.

When this pattern shows up

Practice