LeetCode 767: Reorganize String

Problem Restatement

We are given a string s.

We need to rearrange its characters so that no two adjacent characters are the same.

Return any valid rearrangement.

If no valid rearrangement exists, return an empty string.

The problem allows any correct answer, not one specific output. The official statement says to rearrange the characters so adjacent characters are not equal, or return "" if impossible.

Input and Output

Example function shape:

def reorganizeString(s: str) -> str:
    ...

Examples

Example 1:

s = "aab"

Output:

"aba"

The two a characters are separated by b, so this is valid.

Example 2:

s = "aaab"

Output:

""

There are too many a characters.

No matter how we arrange the string, at least two a characters must be adjacent.

First Thought: Try All Permutations

A direct idea is to generate every permutation of s and return the first one where no adjacent characters are equal.

This is not practical.

A string of length n can have up to:

n!

permutations.

We need a greedy construction.

Key Insight

The character with the largest remaining frequency is the most dangerous one.

If we delay it too much, we may be forced to place it next to itself later.

So at each step, we want to choose the most frequent character that is different from the previously placed character.

A max heap is a good fit for this.

Python has a min heap, so we store negative counts:

(-count, character)

The smallest negative count represents the largest real count.

Impossible Case

Let n = len(s).

If some character appears more than:

(n + 1) // 2

times, then no valid arrangement exists.

Why?

The most frequent character needs enough other characters to separate its copies.

For example:

s = "aaab"

Here a appears 3 times, and n = 4.

The limit is:

(4 + 1) // 2 = 2

Since 3 > 2, it is impossible.

Greedy Heap Method

We keep one previously used character out of the heap for one round.

This prevents the same character from being chosen twice in a row.

At each step:

1. Pop the most frequent available character.
2. Append it to the answer.
3. Decrease its remaining count.
4. Push the previous character back into the heap if it still has remaining count.
5. Store the current character as the previous character for the next round.

This way, the character just used cannot be selected immediately again.

Algorithm

1. Count character frequencies.
2. If the largest frequency is greater than (len(s) + 1) // 2, return "".
3. Build a max heap using negative counts.
4. Keep:
   1. prev_count = 0
   2. prev_char = ""
5. While the heap is not empty:
   1. Pop the most frequent available character.
   2. Append it to the answer.
   3. Decrease its remaining count.
   4. If the previous character still has remaining count, push it back.
   5. Save the current character as previous.
6. Return the joined answer.

Correctness

If a character appears more than (n + 1) // 2 times, there are not enough other characters to separate all copies of it. Therefore, returning "" in that case is correct.

Otherwise, the greedy heap algorithm always chooses the character with the largest remaining frequency among the characters allowed at the current position.

The most recently used character is temporarily withheld from the heap, so the next character chosen cannot be equal to it. Therefore, the algorithm never creates two equal adjacent characters.

After one different character has been placed, the previous character can safely return to the heap, because placing it later will not make it adjacent to its earlier copy.

The algorithm decreases exactly one character count at each step and appends exactly one character. Since every appended character comes from the original frequency counts, and every count is eventually consumed, the returned string contains exactly the same multiset of characters as s.

Thus, when the feasibility condition holds, the algorithm returns a valid reorganization.

Complexity

Let n = len(s).

Since there are only 26 lowercase English letters, the time complexity is effectively O(n).

Implementation

from collections import Counter
import heapq

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

        if max(count.values()) > (len(s) + 1) // 2:
            return ""

        heap = []

        for ch, freq in count.items():
            heapq.heappush(heap, (-freq, ch))

        answer = []
        prev_count = 0
        prev_char = ""

        while heap:
            freq, ch = heapq.heappop(heap)
            answer.append(ch)

            freq += 1

            if prev_count < 0:
                heapq.heappush(heap, (prev_count, prev_char))

            prev_count = freq
            prev_char = ch

        return "".join(answer)

Code Explanation

We first count characters:

count = Counter(s)

Then we check whether a valid answer is possible:

if max(count.values()) > (len(s) + 1) // 2:
    return ""

The heap stores negative frequencies:

heapq.heappush(heap, (-freq, ch))

So the most frequent character is popped first.

The variables:

prev_count = 0
prev_char = ""

store the character used in the previous step, if it still has remaining count.

Inside the loop, we pop the most frequent available character:

freq, ch = heapq.heappop(heap)

Then append it:

answer.append(ch)

Because freq is negative, using one copy means adding 1:

freq += 1

If the previous character still has copies left, push it back now:

if prev_count < 0:
    heapq.heappush(heap, (prev_count, prev_char))

Then store the current character as the previous one:

prev_count = freq
prev_char = ch

This delay prevents the same character from being chosen twice in a row.

Testing

Because many outputs may be valid, tests should check validity rather than exact equality.

from collections import Counter

def is_valid(original: str, result: str) -> bool:
    if result == "":
        max_freq = max(Counter(original).values())
        return max_freq > (len(original) + 1) // 2

    if Counter(original) != Counter(result):
        return False

    for i in range(1, len(result)):
        if result[i] == result[i - 1]:
            return False

    return True

def run_tests():
    s = Solution()

    result = s.reorganizeString("aab")
    assert is_valid("aab", result)

    result = s.reorganizeString("aaab")
    assert result == ""

    result = s.reorganizeString("vvvlo")
    assert is_valid("vvvlo", result)

    result = s.reorganizeString("a")
    assert is_valid("a", result)

    result = s.reorganizeString("aa")
    assert result == ""

    result = s.reorganizeString("abc")
    assert is_valid("abc", result)

    print("all tests passed")

run_tests()

Test meaning: