Reorganize String

Problem Description

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.

Examples

Constraints

• 1 ≤ s.length ≤ 500
• s consists of lowercase English letters

Always Use the Most Frequent Available Character

The failure condition is simple: if any character appears more than (n + 1) / 2 times, no valid rearrangement exists. That single character would need two adjacent slots somewhere.

The greedy approach: always place the most frequent character that wasn’t just used. A max-heap gives you the most frequent character in O(log k) time. After placing it, put it into a “cooldown” state for one step, then re-add it.

Concrete pattern: pop the top two characters from the heap, append them both, then re-push each with decremented counts (if still remaining). This guarantees no two adjacent same characters since you always interleave the two most frequent.

Solution: Max-Heap Greedy

import java.util.*;

class Solution {
    public String reorganizeString(String s) {
        int[] freq = new int[26];
        for (char c : s.toCharArray()) freq[c - 'a']++;

        // max-heap: [frequency, character]
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int i = 0; i < 26; i++) {
            if (freq[i] > 0) heap.offer(new int[]{freq[i], i});
        }

        StringBuilder result = new StringBuilder();

        while (heap.size() >= 2) {
            int[] first = heap.poll();
            int[] second = heap.poll();
            result.append((char)('a' + first[1]));
            result.append((char)('a' + second[1]));
            if (--first[0] > 0) heap.offer(first);
            if (--second[0] > 0) heap.offer(second);
        }

        if (!heap.isEmpty()) {
            int[] last = heap.poll();
            if (last[0] > 1) return ""; // more than one remaining: impossible
            result.append((char)('a' + last[1]));
        }

        return result.toString();
    }
}

import heapq
from collections import Counter

class Solution:
    def reorganizeString(self, s: str) -> str:
        freq = Counter(s)
        max_heap = [(-count, char) for char, count in freq.items()]
        heapq.heapify(max_heap)

        result = []

        while len(max_heap) >= 2:
            count1, char1 = heapq.heappop(max_heap)
            count2, char2 = heapq.heappop(max_heap)
            result.append(char1)
            result.append(char2)
            if count1 + 1 < 0:  # still remaining
                heapq.heappush(max_heap, (count1 + 1, char1))
            if count2 + 1 < 0:
                heapq.heappush(max_heap, (count2 + 1, char2))

        if max_heap:
            count, char = max_heap[0]
            if count < -1:
                return ""  # more than one left: impossible
            result.append(char)

        return ''.join(result)

#include <string>
#include <queue>
#include <vector>

class Solution {
public:
    std::string reorganizeString(std::string s) {
        int freq[26] = {};
        for (char c : s) freq[c - 'a']++;

        // max-heap: {frequency, char_index}
        std::priority_queue<std::pair<int,int>> heap;
        for (int i = 0; i < 26; i++)
            if (freq[i]) heap.push({freq[i], i});

        std::string result;

        while (heap.size() >= 2) {
            auto [f1, c1] = heap.top(); heap.pop();
            auto [f2, c2] = heap.top(); heap.pop();
            result += (char)('a' + c1);
            result += (char)('a' + c2);
            if (f1 - 1 > 0) heap.push({f1 - 1, c1});
            if (f2 - 1 > 0) heap.push({f2 - 1, c2});
        }

        if (!heap.empty()) {
            auto [f, c] = heap.top();
            if (f > 1) return "";
            result += (char)('a' + c);
        }

        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n log k) where k ≤ 26 (number of distinct characters). Each character is pushed/popped at most O(n/k) times.
• Space Complexity: O(k) = O(26) = O(1) for the heap and frequency array.

Where it breaks: popping two characters per iteration means the string always grows in pairs. The edge case is when one character remains at the very end. If it has count > 1, the arrangement is impossible. This check happens after the main loop when the heap has exactly one element left.

Common Mistakes

• Not checking if arrangement is possible upfront. If max frequency > (n+1)/2, return "" immediately. The main loop can also catch this (single element left with count > 1), but early return is cleaner.
• Using a cooldown queue instead of the two-at-a-time approach. The cooldown queue pattern (from Task Scheduler) works but adds complexity. The “pop two, append two” approach is simpler for this specific problem.

Frequently Asked Questions

What is the impossibility condition? If any character appears more than (n + 1) / 2 times (using integer division), it’s impossible. For n = 3 (odd), max allowed is 2. For n = 4 (even), max allowed is 2.

Is there a non-heap solution? Yes. Sort characters by frequency, then interleave: place the most frequent character at even indices (0, 2, 4…), then fill odd indices with the remaining characters. This achieves O(n log n) but avoids the heap.

← All Problems