LeetCode 767 - Reorganize String

Difficulty: 🟡 Medium
Topics: Hash Table, String, Greedy, Sorting, Heap (Priority Queue), Counting

Solution

Problem Understanding

The problem asks us to rearrange the characters of a given string s such that no two adjacent characters are the same. The input is a string of lowercase English letters with a length between 1 and 500. The output should be either a valid rearrangement that satisfies the adjacency constraint or an empty string if no such arrangement is possible.

Key points are that some strings cannot be rearranged to satisfy this condition, particularly when one character appears too frequently. For example, if the most frequent character occurs more than half of the string length rounded up, it is impossible to rearrange without adjacent duplicates. Edge cases include strings with all identical characters, strings of length 1, or strings where multiple characters have the same maximum frequency.

Approaches

The brute-force approach is to generate all permutations of the string and check each one to see if it satisfies the adjacency constraint. This guarantees correctness because it explores every possible rearrangement, but the number of permutations grows factorially with string length, making it infeasible for strings up to length 500.

The optimal approach leverages the observation that we can arrange the characters in a greedy manner, always placing the most frequent remaining character next, but ensuring it is not the same as the previously placed character. To efficiently track the most frequent character at any moment, we use a max heap (priority queue). By popping the highest frequency character, placing it, and then pushing it back with reduced count if necessary, we ensure a valid sequence if possible.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n)	Generate all permutations and check adjacency
Optimal	O(n log k)	O(k)	Use max heap with k unique letters, greedy placement

Algorithm Walkthrough

Count the frequency of each character in the string using a hash map. This helps identify the most frequent characters and supports heap operations.
Initialize a max heap with elements as (frequency, character) pairs, where frequency is negated to simulate a max heap in languages with only min heap support.
Initialize an empty result list to build the rearranged string.
While the heap is not empty, pop the character with the highest remaining frequency.
If the previously placed character exists and still has remaining frequency, push it back into the heap.
Append the chosen character to the result and decrement its frequency.
Keep track of the last used character to prevent consecutive placement.
If at any step, the heap is empty but the previous character still has remaining frequency, return an empty string since no valid rearrangement exists.
Convert the result list to a string and return.

Why it works: This greedy strategy ensures that we always place the character with the highest remaining count while avoiding consecutive duplicates. The max heap guarantees that no character is starved, and the check for the previously used character ensures adjacency rules are never violated.

Python Solution

import heapq
from collections import Counter

class Solution:
    def reorganizeString(self, s: str) -> str:
        freq_map = Counter(s)
        max_heap = [(-count, char) for char, count in freq_map.items()]
        heapq.heapify(max_heap)
        
        prev_count, prev_char = 0, ''
        result = []
        
        while max_heap:
            count, char = heapq.heappop(max_heap)
            result.append(char)
            if prev_count < 0:
                heapq.heappush(max_heap, (prev_count, prev_char))
            count += 1  # decrease count since heap stores negative
            prev_count, prev_char = count, char
        
        result_str = ''.join(result)
        if len(result_str) != len(s):
            return ""
        return result_str

The Python implementation first counts characters and builds a max heap using negative counts. We track the previous character to avoid adjacency conflicts and push it back into the heap only when safe. The loop continues until all characters are placed. The final length check ensures that no characters were left unplaced due to adjacency constraints.

Go Solution

package main

import (
    "container/heap"
    "strings"
)

type CharHeap [][2]interface{} // [0]=count(int), [1]=char(byte)

func (h CharHeap) Len() int { return len(h) }
func (h CharHeap) Less(i, j int) bool { return h[i][0].(int) > h[j][0].(int) }
func (h CharHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *CharHeap) Push(x interface{}) { *h = append(*h, x.([2]interface{})) }
func (h *CharHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func reorganizeString(s string) string {
    freq := make(map[byte]int)
    for i := 0; i < len(s); i++ { freq[s[i]]++ }
    
    h := &CharHeap{}
    heap.Init(h)
    for char, count := range freq { heap.Push(h, [2]interface{}{count, char}) }
    
    var result strings.Builder
    var prevCount int
    var prevChar byte
    
    for h.Len() > 0 {
        item := heap.Pop(h).([2]interface{})
        count := item[0].(int)
        char := item[1].(byte)
        result.WriteByte(char)
        
        if prevCount > 0 { heap.Push(h, [2]interface{}{prevCount, prevChar}) }
        
        count--
        prevCount, prevChar = count, char
    }
    
    if result.Len() != len(s) { return "" }
    return result.String()
}

The Go implementation differs mainly in type handling for the heap and string building. We define a custom heap type to handle the priority queue of characters and use a strings.Builder for efficient string concatenation. Edge cases are handled similarly by checking the final string length.

Worked Examples

Example 1: s = "aab"

Step	Max Heap	Prev Char	Result
Initial	[(-2,'a'),(-1,'b')]	''	''
1	[(-1,'a')]	'a'	'b'
2	[]	'b'	'ba'
3	[]	'a'	'aba'

Output: "aba"

Example 2: s = "aaab"

Step	Max Heap	Prev Char	Result
Initial	[(-3,'a'),(-1,'b')]	''	''
1	[(-2,'a')]	'a'	'b'
2	[]	'a'	cannot proceed, return ""

Output: ""

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log k)	We perform heap operations (push/pop) for each of the n characters, heap size is k unique characters
Space	O(k)	We store frequency counts and a heap of size k, plus O(n) for result string

The reasoning is that k is at most 26 for lowercase English letters, so heap operations are effectively constant, but worst-case complexity is expressed in terms of k.

Test Cases

# provided examples
assert Solution().reorganizeString("aab") in ["aba", "bab"]  # basic valid rearrangement
assert Solution().reorganizeString("aaab") == ""             # impossible case

# boundary cases
assert Solution().reorganizeString("a") == "a"              # single character
assert Solution().reorganizeString("aa") == ""              # two identical characters
assert Solution().reorganizeString("ab") in ["ab", "ba"]    # two distinct characters

# stress / edge
assert Solution().reorganizeString("aabbcc") in ["abcabc", "acbacb", "bacabc", "bcaacb", "cababc", "cbaacb"]  # multiple options
assert Solution().reorganizeString("aaaaabbbbcc") != ""   # complex case with high frequency distribution

Test	Why
"aab"	Tests simple valid rearrangement
"aaab"	Tests impossible rearrangement
"a"	Edge case, single character
"aa"	Edge case, impossible small input
"ab"	Edge case, minimal valid input
"aabbcc"	Tests multiple possible valid outputs
"aaaaabbbbcc"	Tests high frequency character handling

Edge Cases

A key edge case is when a single character dominates the string. For example, "aaaaa" cannot be rearranged, and the implementation correctly returns an empty string. Another edge case is when all characters are distinct, like "abcdef", which trivially allows rearrangement; the heap still correctly outputs a valid string. A third edge case is a string where characters are nearly evenly distributed but one appears slightly more than half, such as "aaabc". The algorithm handles it by detecting that it can no longer place characters without violating adjacency and returns an empty string when necessary. In all cases, the combination of the heap and previous character tracking ensures correctness.