Reorganize String

mediumHeap / Priority Queue119 stepsJava · Python · C++

Rearrange letters so no two neighbours are equal. Greedily place the most frequent remaining letter, but never the one just placed: pop the top two letters from a max-heap, append both, and push them back with one fewer count.

▶ Watch the animated trace

Traced input: s = "aaabbc" → "ababca". Original problem: neetcode.io/problems/reorganize-string

Complexity

BestO(n log 26)

AverageO(n)

WorstO(n)

SpaceO(1)

The heap holds at most 26 letters.

Key idea

If any letter appears more than (n + 1) / 2 times, it's impossible.
Placing the two most frequent letters together each round keeps them from bunching up later.
When only one letter is left, it must have count 1.

Common mistakes

Placing the most frequent letter twice in a row.
Missing the impossibility check, then producing an invalid string.

Solution

Java

String reorganizeString(String s) {
    int[] count = new int[26];
    for (char c : s.toCharArray()) count[c - 'a']++;
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
    for (int i = 0; i < 26; i++) {
        if (count[i] > (s.length() + 1) / 2) {
            return "";
        }
        if (count[i] > 0) heap.offer(new int[]{i, count[i]});
    }
    StringBuilder sb = new StringBuilder();
    while (heap.size() >= 2) {
        int[] a = heap.poll(), b = heap.poll();
        sb.append((char) ('a' + a[0])).append((char) ('a' + b[0]));
        if (--a[1] > 0) heap.offer(a);
        if (--b[1] > 0) heap.offer(b);
    }
    if (!heap.isEmpty()) {
        sb.append((char) ('a' + heap.poll()[0]));
    }
    return sb.toString();
}

Python

def reorganizeString(s: str) -> str:
    count = Counter(s)
    heap = []
    for c, n in count.items():
        if n > (len(s) + 1) // 2:
            return ""
        heapq.heappush(heap, (-n, c))
    out = []
    while len(heap) >= 2:
        n1, a = heapq.heappop(heap)
        n2, b = heapq.heappop(heap)
        out += [a, b]
        if n1 + 1 < 0: heapq.heappush(heap, (n1 + 1, a))
        if n2 + 1 < 0: heapq.heappush(heap, (n2 + 1, b))
    if heap:
        out.append(heapq.heappop(heap)[1])
    return "".join(out)

C++

string reorganizeString(string s) {
    int count[26] = {0};
    for (char c : s) count[c - 'a']++;
    priority_queue<pair<int, char>> heap;
    for (int i = 0; i < 26; i++) {
        if (count[i] > ((int)s.size() + 1) / 2) {
            return "";
        }
        if (count[i] > 0) heap.push({count[i], char('a' + i)});
    }
    string out;
    while (heap.size() >= 2) {
        auto [n1, a] = heap.top(); heap.pop();
        auto [n2, b] = heap.top(); heap.pop();
        out += a; out += b;
        if (--n1 > 0) heap.push({n1, a});
        if (--n2 > 0) heap.push({n2, b});
    }
    if (!heap.empty()) {
        out += heap.top().second;
    }
    return out;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Impossible 3 a's need at least 5 characters.	`s = "aaab"`	`""`
Single character Nothing to separate.	`s = "a"`	`"a"`
Two different Already fine.	`s = "ab"`	`"ab"`
Exactly at the limit a appears (3 + 1) / 2 = 2 times: just possible.	`s = "aab"`	`"aba"`