Reorganize String

Reorganize string so no two adjacent characters are the same

Language Selection

Choose your preferred programming language

Showing: Python

Reorganize String

Problem Statement

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same. Return any possible rearrangement of s or return "" if not possible.

Input/Output Specifications

Input:
- s: String consisting of lowercase English letters
Output: Rearranged string with no adjacent duplicates, or empty string if impossible

Constraints

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

Examples

Example 1:

Input: s = "aab"
Output: "aba"
Explanation: We can rearrange to "aba" so no two adjacent characters are same.

Example 2:

Input: s = "aaab"
Output: ""
Explanation: It's impossible to rearrange since 'a' appears 3 times but string length is 4.

Example 3:

Input: s = "aabbcc"
Output: "ababac" (or "abacab", "babaca", etc.)
Explanation: Multiple valid arrangements exist.

Solution Approaches

Approach 1: Max-Heap with Greedy Strategy (Optimal)

Algorithm Explanation:

Count frequency of each character
Check if reorganization is possible (max frequency ≤ ⌈n/2⌉)
Use max-heap to always pick most frequent available character
Alternate between most frequent and second most frequent characters
Build result string character by character

Implementation:

Python:

import heapq
from collections import Counter

def reorganize_string(s):
    """
    Reorganize string using max-heap and greedy strategy
    Time: O(n log k) where k is number of unique characters
    Space: O(k)
    """
    if not s:
        return ""
    
    # Count character frequencies
    count = Counter(s)
    n = len(s)
    
    # Check if reorganization is possible
    max_freq = max(count.values())
    if max_freq > (n + 1) // 2:
        return ""
    
    # Max-heap (use negative frequencies for min-heap)
    max_heap = [(-freq, char) for char, freq in count.items()]
    heapq.heapify(max_heap)
    
    result = []
    prev_char = None
    prev_freq = 0
    
    while max_heap:
        # Get most frequent character
        freq, char = heapq.heappop(max_heap)
        freq = -freq
        
        result.append(char)
        
        # If we have a previous character to put back, do it now
        if prev_char and prev_freq > 0:
            heapq.heappush(max_heap, (-prev_freq, prev_char))
        
        # Update previous character info
        prev_char = char
        prev_freq = freq - 1
    
    return ''.join(result)

# Alternative implementation with cleaner logic
def reorganize_string_v2(s):
    """
    Alternative reorganize string implementation
    Time: O(n log k)
    Space: O(k)
    """
    count = Counter(s)
    n = len(s)
    
    # Feasibility check
    if max(count.values()) > (n + 1) // 2:
        return ""
    
    # Max-heap
    heap = [(-freq, char) for char, freq in count.items()]
    heapq.heapify(heap)
    
    result = []
    
    while len(heap) >= 2:
        # Take two most frequent characters
        freq1, char1 = heapq.heappop(heap)
        freq2, char2 = heapq.heappop(heap)
        
        # Add them to result
        result.extend([char1, char2])
        
        # Put them back if they still have remaining frequency
        if freq1 < -1:
            heapq.heappush(heap, (freq1 + 1, char1))
        if freq2 < -1:
            heapq.heappush(heap, (freq2 + 1, char2))
    
    # Handle remaining character (if any)
    if heap:
        result.append(heap[0][1])
    
    return ''.join(result)

Java:

import java.util.*;

class Solution {
    /**
     * Reorganize string using max-heap and greedy strategy
     * Time: O(n log k) where k is number of unique characters
     * Space: O(k)
     */
    public String reorganizeString(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        // Count character frequencies
        Map<Character, Integer> count = new HashMap<>();
        for (char c : s.toCharArray()) {
            count.put(c, count.getOrDefault(c, 0) + 1);
        }
        
        int n = s.length();
        int maxFreq = Collections.max(count.values());
        
        // Check feasibility
        if (maxFreq > (n + 1) / 2) {
            return "";
        }
        
        // Max-heap based on frequency
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (a, b) -> Integer.compare(b[1], a[1])
        );
        
        for (Map.Entry<Character, Integer> entry : count.entrySet()) {
            maxHeap.offer(new int[]{entry.getKey(), entry.getValue()});
        }
        
        StringBuilder result = new StringBuilder();
        int[] prev = {0, 0}; // [character, frequency]
        
        while (!maxHeap.isEmpty()) {
            int[] current = maxHeap.poll();
            result.append((char) current[0]);
            
            // Put back previous character if it has remaining frequency
            if (prev[1] > 0) {
                maxHeap.offer(prev);
            }
            
            // Update previous
            current[1]--;
            prev = current;
        }
        
        return result.length() == n ? result.toString() : "";
    }
}

Go:

import (
    "container/heap"
)

type CharFreq struct {
    char rune
    freq int
}

type MaxHeap []CharFreq

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i].freq > h[j].freq } // Max-heap
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MaxHeap) Push(x interface{}) {
    *h = append(*h, x.(CharFreq))
}

func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// reorganizeString - Reorganize string using max-heap
// Time: O(n log k), Space: O(k)
func reorganizeString(s string) string {
    if len(s) == 0 {
        return ""
    }
    
    // Count character frequencies
    count := make(map[rune]int)
    for _, char := range s {
        count[char]++
    }
    
    n := len(s)
    maxFreq := 0
    for _, freq := range count {
        if freq > maxFreq {
            maxFreq = freq
        }
    }
    
    // Check feasibility
    if maxFreq > (n+1)/2 {
        return ""
    }
    
    // Build max-heap
    maxHeap := &MaxHeap{}
    heap.Init(maxHeap)
    
    for char, freq := range count {
        heap.Push(maxHeap, CharFreq{char, freq})
    }
    
    var result []rune
    var prev CharFreq
    
    for maxHeap.Len() > 0 {
        current := heap.Pop(maxHeap).(CharFreq)
        result = append(result, current.char)
        
        // Put back previous character if it has remaining frequency
        if prev.freq > 0 {
            heap.Push(maxHeap, prev)
        }
        
        // Update previous
        current.freq--
        prev = current
    }
    
    if len(result) == n {
        return string(result)
    }
    return ""
}

JavaScript:

class MaxHeap {
    constructor() {
        this.heap = [];
    }
    
    push(element) {
        this.heap.push(element);
        this.bubbleUp();
    }
    
    pop() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();
        
        const max = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();
        return max;
    }
    
    size() {
        return this.heap.length;
    }
    
    bubbleUp() {
        let idx = this.heap.length - 1;
        while (idx > 0) {
            const parentIdx = Math.floor((idx - 1) / 2);
            if (this.heap[parentIdx].freq >= this.heap[idx].freq) break;
            [this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]];
            idx = parentIdx;
        }
    }
    
    bubbleDown() {
        let idx = 0;
        while (2 * idx + 1 < this.heap.length) {
            let maxChildIdx = 2 * idx + 1;
            if (2 * idx + 2 < this.heap.length && 
                this.heap[2 * idx + 2].freq > this.heap[maxChildIdx].freq) {
                maxChildIdx = 2 * idx + 2;
            }
            
            if (this.heap[idx].freq >= this.heap[maxChildIdx].freq) break;
            [this.heap[idx], this.heap[maxChildIdx]] = [this.heap[maxChildIdx], this.heap[idx]];
            idx = maxChildIdx;
        }
    }
}

/**
 * Reorganize string using max-heap and greedy strategy
 * Time: O(n log k) where k is number of unique characters
 * Space: O(k)
 */
function reorganizeString(s) {
    if (!s) return "";
    
    // Count character frequencies
    const count = new Map();
    for (const char of s) {
        count.set(char, (count.get(char) || 0) + 1);
    }
    
    const n = s.length;
    const maxFreq = Math.max(...count.values());
    
    // Check feasibility
    if (maxFreq > Math.ceil(n / 2)) {
        return "";
    }
    
    // Build max-heap
    const maxHeap = new MaxHeap();
    for (const [char, freq] of count) {
        maxHeap.push({char, freq});
    }
    
    let result = "";
    let prev = null;
    
    while (maxHeap.size() > 0) {
        const current = maxHeap.pop();
        result += current.char;
        
        // Put back previous character if it has remaining frequency
        if (prev && prev.freq > 0) {
            maxHeap.push(prev);
        }
        
        // Update previous
        current.freq--;
        prev = current;
    }
    
    return result.length === n ? result : "";
}

C#:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class Solution {
    /// <summary>
    /// Reorganize string using max-heap and greedy strategy
    /// Time: O(n log k) where k is number of unique characters
    /// Space: O(k)
    /// </summary>
    public string ReorganizeString(string s) {
        if (string.IsNullOrEmpty(s)) {
            return "";
        }
        
        // Count character frequencies
        var count = new Dictionary<char, int>();
        foreach (char c in s) {
            count[c] = count.GetValueOrDefault(c, 0) + 1;
        }
        
        int n = s.Length;
        int maxFreq = count.Values.Max();
        
        // Check feasibility
        if (maxFreq > (n + 1) / 2) {
            return "";
        }
        
        // Max-heap using PriorityQueue (higher frequency = higher priority)
        var maxHeap = new PriorityQueue<(char ch, int freq), int>(
            Comparer<int>.Create((a, b) => b.CompareTo(a))
        );
        
        foreach (var kvp in count) {
            maxHeap.Enqueue((kvp.Key, kvp.Value), kvp.Value);
        }
        
        var result = new StringBuilder();
        (char ch, int freq) prev = ('\0', 0);
        
        while (maxHeap.Count > 0) {
            var current = maxHeap.Dequeue();
            result.Append(current.ch);
            
            // Put back previous character if it has remaining frequency
            if (prev.freq > 0) {
                maxHeap.Enqueue(prev, prev.freq);
            }
            
            // Update previous
            prev = (current.ch, current.freq - 1);
        }
        
        return result.Length == n ? result.ToString() : "";
    }
}

Approach 2: Array-based with Odd/Even Positioning

Algorithm Explanation:

Count character frequencies
Place most frequent character at even positions (0, 2, 4, …)
Place remaining characters at odd positions (1, 3, 5, …)
This ensures no two adjacent characters are the same

Implementation:

Python:

def reorganize_string_array(s):
    """
    Reorganize string using array positioning
    Time: O(n)
    Space: O(1) - assuming constant alphabet size
    """
    count = Counter(s)
    n = len(s)
    
    # Check feasibility
    if max(count.values()) > (n + 1) // 2:
        return ""
    
    # Find most frequent character
    max_char = max(count.keys(), key=count.get)
    
    result = [''] * n
    idx = 0
    
    # Place most frequent character at even positions
    for _ in range(count[max_char]):
        result[idx] = max_char
        idx += 2
    
    # Remove most frequent character from count
    del count[max_char]
    
    # Place remaining characters
    for char, freq in count.items():
        for _ in range(freq):
            if idx >= n:
                idx = 1
            result[idx] = char
            idx += 2
    
    return ''.join(result)

Key Insights

Feasibility Condition: Max frequency ≤ ⌈n/2⌉ is necessary and sufficient
Greedy Strategy: Always use most frequent available character
Heap Advantage: Efficiently maintains characters by frequency
Alternative Placement: Even/odd positioning can also work

Edge Cases

Empty String: Return empty string
Single Character: Always possible
Two Characters: Check if frequencies differ by at most 1
Impossible Cases: When most frequent character exceeds limit
All Same Characters: Only possible if length ≤ 1

Test Cases

def test_reorganize_string():
    # Basic cases
    result1 = reorganize_string("aab")
    assert len(result1) == 3 and 'aa' not in result1 and 'bb' not in result1
    
    # Impossible case
    assert reorganize_string("aaab") == ""
    
    # Multiple characters
    result2 = reorganize_string("aabbcc")
    assert len(result2) == 6 and all(result2[i] != result2[i+1] for i in range(5))
    
    # Single character
    assert reorganize_string("a") == "a"
    
    # Empty string
    assert reorganize_string("") == ""
    
    # All same characters (impossible for length > 1)
    assert reorganize_string("aaaa") == ""
    
    # Edge case - exactly at limit
    result3 = reorganize_string("aaab")
    assert result3 == ""  # Max frequency 3 > (4+1)//2 = 2
    
    result4 = reorganize_string("aabb")
    assert len(result4) == 4 and 'aa' not in result4 and 'bb' not in result4
    
    print("All tests passed!")

test_reorganize_string()

Interview Tips

Recognize Greedy Pattern: Always use most frequent available character
Feasibility Check: Explain the mathematical condition upfront
Heap Choice: Max-heap to efficiently get most frequent character
Alternative Approaches: Mention array-based positioning method
Edge Cases: Handle impossible cases and single characters

Follow-up Questions

Distance Constraint: Reorganize with distance k between same characters
Multiple Solutions: Generate all possible reorganizations
Lexicographically Smallest: Find lexicographically smallest valid arrangement
Streaming Input: Handle characters arriving one by one
Different Constraints: What if we want exactly k distance between same chars?

Common Mistakes

Wrong Feasibility Check: Incorrect condition for checking possibility
Heap Type Confusion: Using min-heap instead of max-heap
Previous Character Logic: Not properly handling previously used character
Edge Cases: Not handling single character or empty string
Result Validation: Not checking if final result length matches input

Concept Explanations

Greedy Strategy Correctness: Always choosing the most frequent available character is optimal because it maximizes our flexibility for future choices. If we can place a character now, we should, especially if it’s the most frequent.

Feasibility Mathematics: The condition max_freq ≤ ⌈n/2⌉ comes from the fact that in a valid arrangement, the most frequent character can appear at most every other position, giving us at most ⌈n/2⌉ positions for it.

When to Apply: Use this pattern for string rearrangement problems where you need to avoid adjacent duplicates or maintain certain distance constraints between same characters. The heap-based greedy approach is particularly useful when the constraint involves immediate neighbors.