Reorganize String

Difficulty: Medium Source: NeetCode

Problem

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same. If this is not possible, return an empty string "".

Example 1: Input: s = "aab" Output: "aba"

Example 2: Input: s = "aaab" Output: ""

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters

Prerequisites

Before attempting this problem, you should be comfortable with:

• Greedy algorithms — always placing the most frequent available character
• Max-heap — efficiently retrieving the character with the highest remaining count
• Frequency counting — using Counter from the collections module

1. Brute Force — Interleave Sorted Frequencies

Intuition

Sort characters by frequency descending and try to place them at even positions first, then odd positions. This is the classic “task scheduler” interleave trick. If the most frequent character appears more than (len + 1) // 2 times, it’s impossible.

Algorithm

1. Count character frequencies.
2. If any count exceeds (len(s) + 1) // 2, return "".
3. Sort characters by frequency descending.
4. Place them at even indices 0, 2, 4, ... then odd indices 1, 3, 5, ....

Solution

from collections import Counter

def reorganizeString(s):
    counts = Counter(s)
    n = len(s)

    if max(counts.values()) > (n + 1) // 2:
        return ""

    # Sort by frequency descending
    chars = sorted(counts.keys(), key=lambda c: -counts[c])

    result = [''] * n
    idx = 0  # fill even positions first, then odd

    for char in chars:
        for _ in range(counts[char]):
            if idx >= n:
                idx = 1  # switch to odd positions
            result[idx] = char
            idx += 2

    return ''.join(result)


print(reorganizeString("aab"))   # "aba"
print(reorganizeString("aaab"))  # ""
print(reorganizeString("vvvlo")) # "vlvov" or similar valid answer

Complexity

• Time: O(n log n) — sort dominates
• Space: O(n)

2. Greedy Max-Heap

Intuition

Build a result character by character. At each step, greedily pick the character with the highest remaining count that is not the same as the last character placed. A max-heap makes retrieval of the best candidate O(log k) where k ≤ 26. If we can’t place any character (only the same one remains), it’s impossible.

The trick: after picking a character, hold it aside (don’t push back yet). Pick the next best character, place it, then push the held character back. This ensures we never place two of the same character in a row.

Algorithm

1. Count frequencies. If any > (n + 1) // 2, return "".
2. Build a max-heap (-count, char).
3. While the heap is non-empty: a. Pop (neg_count1, char1) — the most frequent character. b. Append char1 to result. c. If the heap is non-empty, pop (neg_count2, char2) — second most frequent. d. Append char2 to result. e. Push back any characters that still have remaining count.
4. Return the result (check if its length equals n — if not, return "").

Solution

import heapq
from collections import Counter

def reorganizeString(s):
    counts = Counter(s)
    n = len(s)

    # Early impossibility check
    if max(counts.values()) > (n + 1) // 2:
        return ""

    # Max-heap via negation: (-count, char)
    heap = [(-cnt, ch) for ch, cnt in counts.items()]
    heapq.heapify(heap)

    result = []

    while heap:
        neg1, ch1 = heapq.heappop(heap)
        result.append(ch1)

        if heap:
            neg2, ch2 = heapq.heappop(heap)
            result.append(ch2)
            if neg2 + 1 < 0:  # still has remaining count
                heapq.heappush(heap, (neg2 + 1, ch2))

        if neg1 + 1 < 0:  # push ch1 back after ch2 is placed
            heapq.heappush(heap, (neg1 + 1, ch1))

    return ''.join(result) if len(result) == n else ""


print(reorganizeString("aab"))    # "aba"
print(reorganizeString("aaab"))   # ""
print(reorganizeString("aabb"))   # "abab" or "baba"
print(reorganizeString("vvvlo"))  # valid arrangement like "vlvov"

Complexity

• Time: O(n log k) where k ≤ 26 — n characters placed, each heap op is O(log k)
• Space: O(n) for the result

Common Pitfalls

Forgetting the impossibility check. If any character appears more than (len + 1) // 2 times, no valid arrangement exists. Always check this first — it saves time and avoids an infinite loop in naive implementations.

Pushing the current character back too early. In the pair-based approach, push ch1 back only after ch2 has been appended. If you push it back before placing ch2, the heap may immediately pop ch1 again and place it twice in a row.

Returning the result without length validation. In edge cases, the result might be shorter than n (e.g., only one character type remains and it’s the last). Check len(result) == n before returning.