#767 Reorganize String - Solution

Reorganize String asks you to rearrange characters so that no two adjacent characters are the same. The key idea is to always place the characters with the highest remaining frequency while ensuring they are separated. A common strategy is to count frequencies using a hash map or array, then use a max heap (priority queue) to repeatedly select the most frequent characters.

At each step, take the character with the highest frequency, append it to the result, decrease its count, and temporarily hold it until the next character is placed. This prevents immediate reuse and ensures spacing between identical characters. If the maximum frequency exceeds (n + 1) / 2, reorganization becomes impossible.

Another variation sorts characters by frequency and fills even indices first, then odd indices. Both approaches rely on greedy placement based on counts. Typical complexity is O(n log k) using a heap (where k is the number of distinct characters) with O(k) extra space.

Approach	Time Complexity	Space Complexity
Max Heap (Priority Queue) with Frequency Counting	O(n log k)	O(k)
Greedy Placement with Sorting / Counting	O(n + k log k)	O(k)

Solutions (4)

Greedy Heap Approach

This approach utilizes a max heap to always place the character with the maximum frequency next, ensuring that no two adjacent characters are the same. If the character frequency is more than half of the string length, it is impossible to rearrange.

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(n)

Python Java

1import java.util.PriorityQueue;
2import java.util.HashMap;
3
4public class ReorganizeString {
5    public String reorganizeString(String s) {
6        HashMap<Character, Integer> frequencyMap = new HashMap<>();
7        for (char c : s.toCharArray()) {
8            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
9        }
10
11        PriorityQueue<Character> maxHeap = new PriorityQueue<>((a, b) -> frequencyMap.get(b) - frequencyMap.get(a));
12        maxHeap.addAll(frequencyMap.keySet());
13
14        StringBuilder result = new StringBuilder();
15        while (maxHeap.size() > 1) {
16            char first = maxHeap.remove();
17            char second = maxHeap.remove();
18            result.append(first);
19            result.append(second);
20            frequencyMap.put(first, frequencyMap.get(first) - 1);
21            frequencyMap.put(second, frequencyMap.get(second) - 1);
22
23            if (frequencyMap.get(first) > 0) maxHeap.add(first);
24            if (frequencyMap.get(second) > 0) maxHeap.add(second);
25        }
26
27        if (!maxHeap.isEmpty()) {
28            char last = maxHeap.remove();
29            if (frequencyMap.get(last) > 1) return "";
30            result.append(last);
31        }
32
33        return result.toString();
34    }
35}

Explanation

This Java solution uses a max heap to always choose the most frequent character available. We insert characters alternately and handle the case where we may have an odd leftover character at the end.

Counting and Greedy Approach

This approach utilizes a direct counting mechanism and attempts to place characters in a greedy manner, utilizing an array to keep track of placement positions for the most frequent characters first.

Time Complexity: O(n) due to linear scanning and filling. Space Complexity: O(1) since we use a fixed-size count array.

C C++

1#include <string>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6string reorganizeString(string s) {
    vector<int> count(26, 0);
    int n = s.size();
    for (char c : s) count[c - 'a']++;

    int maxCount = *max_element(count.begin(), count.end());
    if (maxCount > (n + 1) / 2) return "";

    string result(n, ' ');
    int evenIndex = 0, oddIndex = 1;
    for (int i = 0; i < 26; i++) {
        while (count[i] > 0 && count[i] <= n / 2 && oddIndex < n) {
            result[oddIndex] = 'a' + i;
            oddIndex += 2;
            count[i]--;
        }
        while (count[i] > 0) {
            result[evenIndex] = 'a' + i;
            evenIndex += 2;
            count[i]--;
        }
    }

    return result;
}