Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Reorganize String
• Main tags: Hash Table, String, Greedy, Heap, Counting

What the problem is really asking

The input is a string s. The task is to rearrange its characters so that no two adjacent characters are equal. If no such rearrangement exists, return the empty string. Any valid rearrangement is accepted.

The important point is that the exact order does not matter. This is not a sorting problem. It is a spacing problem: the most frequent character needs enough other characters between its copies.

For example, aab can become aba. But aaab cannot be fixed, because three copies of a would need at least two non-a characters to separate them, and there is only one.

The key feasibility rule

Let n be the string length and let max_count be the count of the most common character.

The string can be reorganized only if:

max_count <= (n + 1) // 2

This is the whole impossibility test.

Why? The most frequent character needs to occupy separated slots. In a string of length n, the largest number of non-adjacent positions available to one character is the number of even-indexed slots, which is (n + 1) // 2.

If a character appears more often than that, at least two of its copies must be adjacent. If every character fits within that bound, a greedy construction can always place characters without creating adjacent duplicates.

Greedy construction with a max heap

The practical strategy is to always place the character with the highest remaining count, but never allow the same character to be used twice in a row.

A max heap gives direct access to the character that is currently most urgent to place. Python only has a min heap, so the code stores negative counts.

The clean trick is to hold back the character just used for one turn. That character is not pushed back into the heap immediately, which prevents the next step from choosing it again. After a different character is placed, the held character can return to the heap if it still has remaining copies.

That gives this rhythm:

1. Pop the most frequent available character.
2. Append it to the answer.
3. Decrease its remaining count.
4. Push back the previously used character, if it still has copies left.
5. Hold the current character out until the next step.

Because the impossible case was already ruled out, this process can consume all characters and produce a valid string.

How to derive this in an interview

Start with the failure case. Ask what makes the problem impossible. The only way to fail is for one character to appear so often that the rest of the string cannot separate its copies. That leads directly to the max_count <= ceil(n / 2) rule.

After that, focus on construction. Since the most frequent remaining character is always the one most likely to cause trouble later, place it early. But because using the same character twice in a row is forbidden, temporarily remove the character just placed from the candidate pool. A heap plus one held-back character expresses exactly that idea.

This is a good interview answer because it explains both halves of the problem: why an answer may not exist, and why the greedy construction is safe when it does.

Python solution

from collections import Counter
from heapq import heapify, heappop, heappush


class Solution:
    def reorganizeString(self, s: str) -> str:
        character_counts = Counter(s)

        if not self._is_reorganization_possible(character_counts, len(s)):
            return ""

        max_heap = self._build_max_heap(character_counts)
        result_chars: list[str] = []

        held_count = 0
        held_char = ""

        while max_heap:
            current_count, current_char = heappop(max_heap)
            result_chars.append(current_char)

            # Counts are negative in the heap, so adding 1 means "use one copy."
            current_count += 1

            # The previously used character is safe to offer again only after
            # we have placed a different character.
            if held_count < 0:
                heappush(max_heap, (held_count, held_char))

            held_count = current_count
            held_char = current_char

        return "".join(result_chars)

    @staticmethod
    def _is_reorganization_possible(
        character_counts: Counter,
        string_length: int,
    ) -> bool:
        max_allowed_count = (string_length + 1) // 2
        return all(
            count <= max_allowed_count
            for count in character_counts.values()
        )

    @staticmethod
    def _build_max_heap(character_counts: Counter) -> list[tuple[int, str]]:
        max_heap = [
            (-count, character)
            for character, count in character_counts.items()
        ]
        heapify(max_heap)
        return max_heap

Time complexity is O(n log k), where n is the string length and k is the number of distinct characters. Space complexity is O(n + k) for the output and heap. If the alphabet is fixed, such as lowercase English letters, the heap factor is effectively constant and the runtime is linear in n.

Interview follow-ups

Can this be solved without a heap?

Yes. If the alphabet is small or fixed, count every character, sort characters by descending frequency, and fill the answer array at every other index: 0, 2, 4, and so on. When the end is reached, continue with odd indices: 1, 3, 5, and so on.

This works because the feasibility rule guarantees the most frequent character fits into the separated even slots. Placing high-frequency characters first prevents them from being forced together later. The resulting complexity is O(n + k log k) if the distinct characters are sorted, or O(n + k) with a fixed-size counting array.

What if the interviewer asks for the lexicographically smallest valid answer?

The heap solution returns any valid answer, not necessarily the smallest one. For the lexicographically smallest valid string, build the answer from left to right and try candidate characters in sorted order. A candidate can be committed only if it is different from the previous output character and the remaining multiset can still be completed.

The feasibility check after choosing a candidate is similar to the original rule, but it must account for the previous character. If the previous character still has remaining copies, it has fewer legal slots because the next position cannot use it. With a fixed alphabet, scanning all counts after each tentative choice is simple and keeps the code understandable. The tradeoff is higher runtime: O(n * k^2) in the most direct version, or better with additional bookkeeping.

How would this change if identical characters had to be at least d positions apart?

This becomes the common “rearrange string k distance apart” variant. The same max-heap idea still applies, but instead of holding the previous character for one turn, keep used characters in a cooldown queue for d turns.

At each step, pop the highest-count available character from the heap, append it, decrement its count, and put it into the cooldown queue with the step when it becomes available again. Once a cooled character is far enough away, push it back into the heap. If the heap becomes empty before the answer reaches length n, the reorganization is impossible. The runtime remains O(n log k), and the extra queue uses O(k) space.

How can you prove the greedy heap method is safe?

The impossibility rule handles the only structural blocker: one character being too frequent to separate. Once that is ruled out, the most urgent remaining character should be placed as soon as it is legal, because delaying it only makes future spacing harder.

The held-back character prevents the only local violation, which is repeating the character just placed. Every other character in the heap is legal for the next position. Choosing the highest-count legal character keeps the remaining counts balanced, so no character can suddenly exceed the available separated slots unless it already violated the feasibility rule earlier.

What if only a yes-or-no answer is needed?

Then no construction is necessary. Count the characters and return whether the largest count is at most (n + 1) // 2.

That works because the bound is both necessary and sufficient for this exact problem. The check takes O(n) time and O(k) space, and it is often the best first observation to state before writing the full rearrangement algorithm.