Reorganize String

Problem

Rearrange the characters of s so no two adjacent characters are equal. Return any valid rearrangement, or "" if impossible.

Constraints

• 1 ≤ s.length ≤ 500

Approach — Heaps / Top-K

This is a Heaps / Top-K problem. The idea: use a heap so the min, max, or top-k element stays reachable in O(log n) per operation. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n log k) time.

Solution code

Python

class Solution:
    def reorganizeString(self, s):
        from collections import Counter
        import heapq
        c = Counter(s)
        if max(c.values()) > (len(s) + 1) // 2:
            return ''
        heap = [(-v, ch) for ch, v in c.items()]
        heapq.heapify(heap)
        res = []
        prev = None
        while heap:
            v, ch = heapq.heappop(heap)
            res.append(ch)
            if prev and prev[0] < 0:
                heapq.heappush(heap, prev)
            prev = (v + 1, ch)
        return ''.join(res)

Java

class Solution {
    public String reorganizeString(String s) {
        // Count each character.
        int[] count = new int[26];
        for (char ch : s.toCharArray()) {
            count[ch - 'a']++;
        }

        // Impossible if any letter occurs more than (n + 1) / 2 times.
        // Max-heap of (count, char). Always lay down the highest-count
        // letter that ISN'T the one we just placed.
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0) {
                if (count[i] > (s.length() + 1) / 2) {
                    return "";
                }
                heap.offer(new int[] { count[i], i });
            }
        }

        StringBuilder sb = new StringBuilder();
        while (heap.size() >= 2) {
            int[] first = heap.poll();
            int[] second = heap.poll();
            sb.append((char) ('a' + first[1]));
            sb.append((char) ('a' + second[1]));
            if (--first[0] > 0) {
                heap.offer(first);
            }
            if (--second[0] > 0) {
                heap.offer(second);
            }
        }
        if (!heap.isEmpty()) {
            sb.append((char) ('a' + heap.poll()[1]));
        }
        return sb.toString();
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.