767. Reorganize String

The Reorganize String problem is a common interview question that tests how well you handle greedy construction under strict constraints. Many candidates start by shuffling characters randomly, only to realize that duplicates can easily force identical letters to end up adjacent. This problem pushes you to think in terms of character frequencies and always choosing the best next option to keep the arrangement valid. It’s a great exercise in using a priority queue to build a string while avoiding impossible states.

Problem statement

You are given a lowercase string s, and you need to rearrange its characters so that no two neighboring characters are the same. If such a rearrangement exists, return any valid one; otherwise, return an empty string.

Constraints:

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

Examples

Naive approach: Trying all permutations

A straightforward idea is to generate all permutations of the string (or keep shuffling) until you find one where no two adjacent characters are the same. The problem is that permutations grow factorially, so even a small increase in n makes the search blow up. And even with “smart” backtracking, you often end up exploring many nearly identical partial strings, repeatedly failing for the same reason, usually because one high-frequency character can’t be placed without causing collisions.

Optimized approach using Max-Heap Greedy insight

A better way is to treat each character like a “task” that must be scheduled a certain number of times, with the constraint that the same task cannot run twice in a row. The hardest character to deal with is always the one that appears the most, so we want to place the currently most frequent character whenever possible.

To do this efficiently, we store characters in a max-heap keyed by remaining frequency. Each step, we pick the character with the highest remaining count, append it to the result, and decrease its count. To prevent duplicates, we keep the previously used character out of the heap for one step (if it still has remaining occurrences). After placing a different character, we safely push the previous one back into the heap.

If we ever reach a point where the heap is empty but we still have a “held-back” character with remaining count, then there’s no valid next move, meaning no rearrangement can satisfy the rule, so we return an empty string.

Solution steps

1. Create a frequency map freq for all characters in s.
2. Create a heap where each entry is (-count, ch) so the character with the highest remaining count comes out first.
3. Create an empty list result to build the answer.
4. Initialize prev_char = None and prev_count = 0 to track the last used character that may need to be pushed back.
5. While the heap is not empty:
   1. Pop the character with the highest remaining count.
   2. Append it to the result.
   3. Since you used one instance, increase its (negative) count by +1 (moving it toward zero).
   4. If prev_char still has remaining occurrences (prev_count < 0), push it back into the heap.
   5. Set prev_char and prev_count to the character you just used and its updated count.
6. If you successfully build a string of length len(s), return it; otherwise return "".

To better understand the algorithm, let’s walk through an illustration example below.

1 / 8

Python code implementation

Let’s look at the code for this solution below:

from collections import Counter
import heapq


def reorganizeString(s):
    freq = Counter(s)

    # Max-heap by frequency: store as (-count, char)
    heap = [(-count, ch) for ch, count in freq.items()]
    heapq.heapify(heap)

    result = []
    prev_count, prev_ch = 0, None  # prev_count is negative when it still has remaining

    while heap:
        count, ch = heapq.heappop(heap)

        # Place current character
        result.append(ch)

        # We used one occurrence: move count toward zero
        count += 1  # since count is negative, +1 means "one less remaining"

        # Push back the previous character if it still has remaining occurrences
        if prev_count < 0:
            heapq.heappush(heap, (prev_count, prev_ch))

        # Current character becomes the "previous" (held out of heap for one step)
        prev_count, prev_ch = count, ch

    # If we placed all characters, it's valid; otherwise it's impossible
    return "".join(result) if len(result) == len(s) else ""
    
def main():
    test_cases = [
        "aab",
        "aaab",
        "vvvlo",
        "aaabc",
        "bbbbccdde",
    ]

    for i, s in enumerate(test_cases, 1):
        print(f"Test {i}:\ts = '{s}'")
        out = reorganizeString(s)
        print("\tResult:", out)
        print("-"*75)


if __name__ == "__main__":
    main()

Time complexity

The time complexity is O(n log a) where n is the length of the string and a is the number of distinct characters. Each character placement involves heap operations, and the heap size is at most the number of unique letters (up to 26 here), so the log factor is small but still present.

Space complexity

The space complexity is O(a) for the frequency map and heap, plus O(n) for the output string being built. In the worst case (all characters distinct), the heap and counter both track all distinct characters.

Edge cases

• Single character string
  • Example: "a"
  • Why it works: the result is "a", and there are no adjacent pairs to violate the rule.
• All characters the same
  • Example: "aaaa"
  • Why it works: the algorithm will place one 'a', then the heap becomes empty while 'a' still remains held as prev, so the final length check fails and returns "".
• One character dominates but still possible
  • Example: "aaabc"
  • Why it works: the heap keeps selecting 'a' often, but always forces an alternate character between consecutive 'a' placements when available.
• Many distinct characters
  • Example: "abcde"
  • Why it works: every placement is safe, and the heap simply returns characters until exhausted.

Common pitfalls

• Not preventing immediate reuse of the last character
  • Mistake: pop the max character repeatedly without a “cooldown,” which can create adjacent duplicates.
• Forgetting to push the previously used character back
  • Mistake: holding prev but never re-inserting it causes missing characters and incorrect results.
• Returning the built string without validating length
  • Mistake: in impossible cases, you can end early; the length check is what correctly turns that into "".
• Overcomplicating with manual “fill even indices then odd indices” without careful checks
  • Mistake: can work, but off-by-one errors and incorrect feasibility handling are common in interviews.