LeetCode Solutions Blog

Reorganize String

Number: 778

Difficulty: Medium

Paid? No

Problem Description

Rearrange the characters in the given string such that no two adjacent characters are the same. If such a rearrangement is not possible, return an empty string.

Key Insights

Count the frequency of each character.
A valid reorganization is impossible if any character’s frequency exceeds half of the string length (rounded up).
Use a max heap (priority queue) to always choose the character with the highest remaining frequency.
Place the most frequent character and then pick the next most frequent; add the previous character back if it still has remaining frequency.
This greedy strategy ensures that the most frequent characters are always spaced apart.

Space and Time Complexity

Time Complexity: O(n log k), where n is the length of the string and k is the number of unique characters. Space Complexity: O(k) for the frequency map and heap.

Solution

The solution begins by counting the frequency of each character in the string. If any character appears more than (n + 1) / 2 times, then a valid arrangement is impossible.

Next, use a max heap to always select the character with the highest remaining frequency. Repeatedly extract the top two characters from the heap, append them to the result, and then reduce their frequency. If a character still has a positive frequency after decrementing, push it back into the heap.

This greedy strategy guarantees that no two adjacent characters are the same, because by always pairing the most frequent remaining characters, they are distributed as evenly as possible.

Code Solutions

# Python solution using heapq. The heap is simulated as a max heap by storing negative frequencies.
import heapq

def reorganizeString(s: str) -> str:
    # Count frequency of each character.
    frequency = {}
    for char in s:
        frequency[char] = frequency.get(char, 0) + 1

    # Check if reorganization is possible.
    max_allowed = (len(s) + 1) // 2
    for count in frequency.values():
        if count > max_allowed:
            return ""
    
    # Build a max heap based on frequency.
    max_heap = [(-count, char) for char, count in frequency.items()]
    heapq.heapify(max_heap)
    
    result = []
    prev_count, prev_char = 0, ''
    
    # Process the heap.
    while max_heap:
        count, char = heapq.heappop(max_heap)
        # Append the current character to the result.
        result.append(char)
        
        # If there is a previous character leftover, push it back into the heap.
        if prev_count < 0:
            heapq.heappush(max_heap, (prev_count, prev_char))
        
        # Update previous character info: decrement the count.
        count += 1  # since count is negative, incrementing moves it towards zero.
        prev_count, prev_char = count, char
        
    return "".join(result)

# Example usage:
print(reorganizeString("aab"))  # Expected Output: "aba"
print(reorganizeString("aaab")) # Expected Output: ""