Reorganize String: Greedy Character Spacing

Reorganize String (LeetCode 767) asks you to rearrange a string so that no two adjacent characters are the same. If no valid rearrangement exists, return an empty string. This is a classic greedy problem where frequency counting meets heap-based selection.

Examples:

• "aab" returns "aba"
• "aaab" returns "" (impossible)

The core challenge is figuring out which character to place next. You always want to pick the most frequent remaining character, but you cannot pick the same character you just placed. That constraint is what makes this a greedy heap problem rather than a simple sort.

The approach

The key insight is that the most frequent character drives the arrangement. If any single character appears more than (n + 1) // 2 times (where n is the string length), it is impossible to space it out. Otherwise, you can always build a valid result by greedily picking the two most frequent characters and alternating them.

Algorithm steps:

1. Count character frequencies using a hash map
2. Check if any character appears more than (n + 1) // 2 times. If so, return ""
3. Build a max heap from the frequencies (using negative counts for Python's min heap)
4. Pop two characters at a time, append both to the result
5. Push them back with decremented counts if they still have remaining occurrences

By always popping two at a time, you guarantee the same character never lands in consecutive positions. The most frequent character gets placed first in each pair, and the second most frequent fills the gap.

Visual walkthrough

Here is how the algorithm processes "aab" step by step. Watch how the heap shrinks and the result string grows with each iteration.

Notice that each pair of pops produces two characters that are guaranteed to be different. The only time a single pop happens is at the very end, when one character has exactly one occurrence left.

Python solution

import heapq
from collections import Counter

def reorganizeString(s):
    counts = Counter(s)
    max_heap = [(-count, char) for char, count in counts.items()]
    heapq.heapify(max_heap)

    if -max_heap[0][0] > (len(s) + 1) // 2:
        return ""

    result = []
    while len(max_heap) >= 2:
        count1, char1 = heapq.heappop(max_heap)
        count2, char2 = heapq.heappop(max_heap)
        result.append(char1)
        result.append(char2)
        if count1 + 1 < 0:
            heapq.heappush(max_heap, (count1 + 1, char1))
        if count2 + 1 < 0:
            heapq.heappush(max_heap, (count2 + 1, char2))

    if max_heap:
        result.append(max_heap[0][1])

    return "".join(result)

1. Count frequencies with Counter(s). This gives you a dictionary of character counts in O(n) time.
2. Build the max heap by negating counts (Python only has a min heap). Each entry is (-count, char).
3. Feasibility check: if the top of the heap has a count greater than (n + 1) // 2, return "" immediately.
4. Main loop: pop two elements, append both characters to the result. Decrement their counts and push back any that still have remaining occurrences.
5. Handle the leftover: if the heap has exactly one element left, append it. This only happens when the string has odd length and the last character appears once.

Complexity analysis

Time: O(n log k) where n is the length of the string and k is the number of unique characters (at most 26). Each character gets pushed and popped from the heap at most once per occurrence, and each heap operation costs O(log k).

Space: O(k) for the heap and counter. Since k is bounded by 26 for lowercase English letters, this is effectively O(1) extra space.

Building blocks

Frequency counting

Counting how often each character appears is the first step in many string problems. You will see this same Counter pattern in Top K Frequent Elements, Valid Anagram, and Group Anagrams. The frequency map is what transforms the raw string into structured data you can reason about.

Max heap / greedy selection

The max heap lets you always grab the most frequent remaining character in O(log k) time. This greedy choice works because placing the highest-frequency character first minimizes the risk of getting stuck with consecutive duplicates later. The same "pop the largest, use it, push it back" pattern appears in Task Scheduler and priority-queue problems throughout LeetCode.

Edge cases

• Single character string: "a" returns "a". Only one character, so no adjacency conflict is possible.
• All identical characters: "aaa" returns "". The max frequency (3) exceeds (3 + 1) // 2 = 2, so reorganization is impossible.
• Two characters with equal frequency: "aabb" returns "abab" or "baba". Both are valid since neither character dominates.
• Already valid string: "abc" returns "abc" (or any permutation). When all characters appear once, any arrangement works.

From understanding to recall

The tricky part to remember is the loop structure: pop two, append two, push back survivors. It is easy to accidentally pop one at a time and then check adjacency manually, which leads to messy code. The two-at-a-time pattern is cleaner because it inherently prevents consecutive duplicates. The other detail that slips is the feasibility check formula. Remember that (n + 1) // 2 is the maximum number of "odd positions" in the string, and the most frequent character must fit within those slots.

Related posts

• Task Scheduler - Same greedy heap approach for spacing elements with cooldown periods
• Top K Frequent Elements - Uses frequency counting and heap selection
• Sort Characters by Frequency - Frequency-based character reordering