Reorganize String — Solution

Problem

Rearrange the characters of a string so that no two adjacent characters are identical. Return any valid rearrangement, or an empty string if none exists.

• Input: s = "aab"
• Output: "aba"
• Explanation: Placing 'b' between the two 'a's satisfies the no-adjacent-duplicates rule.

When one character is too frequent, no valid arrangement is possible:

• Input: s = "aaab"
• Output: ""
• Explanation: 'a' appears 3 times in a 4-character string — any arrangement forces at least two 'a's to be adjacent.

Intuition

If any character appears more than ⌈n/2⌉ times, the answer is impossible — there aren't enough other characters to keep its copies separated. When a valid arrangement exists, the right greedy strategy is to always place the most-frequent remaining character next. The one constraint: after placing a character, hold it for exactly one step before reusing it. This cooldown prevents consecutive duplicates, and always choosing the highest-frequency available character ensures no single character falls so far behind that the arrangement becomes impossible later.

Solution — Greedy Max-Heap with Cooldown

Use a max-heap ordered by frequency. At each step, pop the most-frequent available character, append it to the result, and hold it for one round before returning it to the heap.

1. Count the frequency of every character.
2. Push all (frequency, character) pairs onto a max-heap.
3. Track the character currently on cooldown from the previous step.
4. Each iteration: pop the most-frequent available character, append it to the result.
5. Return the cooled-down character from the prior step back to the heap.
6. If the final result length equals the input length, return it — otherwise return "".

1import heapq
2from collections import Counter
3
4def reorganizeString(s: str) -> str:
5    freq_map = Counter(s)
6    # negate frequencies since Python's heapq is a min-heap
7    max_heap = [(-count, char) for char, count in freq_map.items()]
8    heapq.heapify(max_heap)
9
10    result = []
11    prev_count, prev_char = 0, ''  # character currently on one-step cooldown
12
13    while max_heap:
14        count, char = heapq.heappop(max_heap)
15        result.append(char)
16        if prev_count < 0:  # previous char's cooldown has expired; make it available again
17            heapq.heappush(max_heap, (prev_count, prev_char))
18        prev_count = count + 1  # one fewer remaining (count is negative, so +1 brings it closer to 0)
19        prev_char = char
20
21    return ''.join(result) if len(result) == len(s) else ''

Time: O(n log k) where k ≤ 26 distinct characters — effectively O(n) for lowercase English input.
Space: O(k) for the heap plus O(n) for the output string.

Complexity Summary

Common Mistakes

• Not holding the previous character for a full step — pushing a character back into the heap in the same round you popped it skips the cooldown entirely, allowing the same character to be placed twice in a row.
• Off-by-one on the feasibility bound — checking max_freq > n // 2 instead of max_freq > (n + 1) // 2 incorrectly rejects valid inputs like "aab" where 'a' appears ⌈3/2⌉ = 2 times.
• Forgetting to negate in Python — heapq is a min-heap; omitting the negation means you always pick the least-frequent character first, producing wrong arrangements or short outputs.
• Returning the raw result without length validation — when no valid arrangement exists, the heap empties before all characters are placed and the result is shorter than the input. Always verify len(result) == len(s).
• Pushing the cooled-down character at the wrong moment — the previous character must re-enter the heap before the current pop so it can compete for the next slot; pushing it after the pop means it misses the current round.

Related Problems

• sort-characters-by-frequency — groups characters by frequency using the same counting approach, without the adjacency constraint
• top-k-frequent-elements — frequency counting with a max-heap to extract the top-k entries
• top-k-frequent-words — extends the top-k heap pattern to strings with a custom tie-breaking comparator
• last-stone-weight — max-heap used to greedily process the two largest remaining values each round
• kth-largest-element-in-an-array — heap-based selection for order statistics