Reorganize String

MEDIUM✓ CHIP-TIMEDLC #767 — FULL STATEMENT ↗

The drill: Reshuffle a string's letters so no two identical letters end up next to each other — return one valid arrangement if any exists, or empty if the letters are too lopsided to ever separate.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A string of lowercase letters arrives, and the goal is rearranging its own letters — not choosing new ones — so that no two identical letters end up adjacent.

Some inputs are simply too lopsided to ever separate, when one letter alone makes up more than half the string; in that case the expected answer is an empty result signaling impossibility.

Any valid rearrangement is accepted when one exists — there's no single correct output, just a check that no two neighbors in the returned string match.

EX 01

s = "aa"

→ [""]

TWO IDENTICAL LETTERS, IMPOSSIBLE

EX 02

s = "aaab"

→ [""]

ONE LETTER IS OVER HALF THE STRING, IMPOSSIBLE

EX 03

s = "a"

→ ["a"]

MINIMUM SIZE, TRIVIALLY VALID

string lengths run up to a few thousand characters
only lowercase letters appear in the input
impossible inputs expect an empty string back
any valid no-adjacent-repeat arrangement is accepted

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A letter that shows up more than half the string (rounding up) can never be fully separated from itself — check that ceiling first before trying to build anything.

HINT 2 THE STRUCTURE

Placing the single most frequent remaining letter at every step, as long as it's not the letter you just placed, keeps every other letter's options open the longest.

HINT 3 ONE STEP FROM THE ANSWER

Keep letter counts in a max-heap. Pop the most frequent, place it, and if it's the same letter you just placed, temporarily pop the second-most-frequent instead — then push whatever still has count left back in.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE MAX-HEAP SHUFFLEPATTERN · MAX-HEAP OF LETTER COUNTSs = "aaabbc" — counts a=3, b=2, c=1

STEP 1

Counts start a=3, b=2, c=1 over 6 letters. The heaviest letter, 3, isn't over half of 6, so a valid arrangement exists.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/reorganize-string.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def reorganizeString(self, s: str) -> str:
        counts = collections.Counter(s)
        n = len(s)
        if counts and max(counts.values()) > (n + 1) // 2:
            return ""

        heap = [(-c, ch) for ch, c in counts.items()]
        heapq.heapify(heap)
        result = []
        while heap:
            c1, ch1 = heapq.heappop(heap)
            if result and result[-1] == ch1:
                if not heap:
                    return ""
                c2, ch2 = heapq.heappop(heap)
                result.append(ch2)
                c2 += 1
                if c2 < 0:
                    heapq.heappush(heap, (c2, ch2))
                heapq.heappush(heap, (c1, ch1))
            else:
                result.append(ch1)
                c1 += 1
                if c1 < 0:
                    heapq.heappush(heap, (c1, ch1))
        return "".join(result)

TIME O(N LOG 26)SPACE O(26)PYTHON · RACE PACE · 27 LN

class Solution:
    def reorganizeString(self, s: str) -> str:
        counts = collections.Counter(s)
        letters = sorted(counts)  # fixed scan order
        n = len(s)

        def backtrack(remaining, last):
            if remaining == 0:
                return ""
            for ch in letters:
                if counts[ch] > 0 and ch != last:
                    counts[ch] -= 1
                    rest = backtrack(remaining - 1, ch)
                    if rest is not None:
                        return ch + rest
                    counts[ch] += 1  # backtrack, this placement led nowhere
            return None

        result = backtrack(n, "")
        return result if result is not None else ""

TIME O(N!) WORST CASESPACE O(N)PYTHON · TRAINING PACE · 20 LN

class Solution {
    public String reorganizeString(String s) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }
        int n = s.length();
        int maxCount = 0;
        for (int c : counts) {
            maxCount = Math.max(maxCount, c);
        }
        if (maxCount > (n + 1) / 2) {
            return "";
        }

        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[1] - a[1]); // [charIndex, count]
        for (int i = 0; i < 26; i++) {
            if (counts[i] > 0) {
                heap.offer(new int[] { i, counts[i] });
            }
        }

        StringBuilder sb = new StringBuilder();
        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            if (sb.length() > 0 && sb.charAt(sb.length() - 1) - 'a' == top[0]) {
                if (heap.isEmpty()) {
                    return "";
                }
                int[] second = heap.poll();
                sb.append((char) ('a' + second[0]));
                second[1]--;
                if (second[1] > 0) {
                    heap.offer(second);
                }
                heap.offer(top);
            } else {
                sb.append((char) ('a' + top[0]));
                top[1]--;
                if (top[1] > 0) {
                    heap.offer(top);
                }
            }
        }
        return sb.toString();
    }
}

TIME O(N LOG 26)SPACE O(26)JAVA · RACE PACE · 47 LN

class Solution {
    public String reorganizeString(String s) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }
        List<Character> letters = new ArrayList<>();
        for (char c = 'a'; c <= 'z'; c++) {
            if (counts[c - 'a'] > 0) {
                letters.add(c);
            }
        }
        char[] buffer = new char[s.length()];
        return backtrack(0, s.length(), '\0', letters, counts, buffer) ? new String(buffer) : "";
    }

    private boolean backtrack(int pos, int n, char last, List<Character> letters, int[] counts, char[] buffer) {
        if (pos == n) {
            return true;
        }
        for (char ch : letters) {
            if (counts[ch - 'a'] > 0 && ch != last) {
                counts[ch - 'a']--;
                buffer[pos] = ch;
                if (backtrack(pos + 1, n, ch, letters, counts, buffer)) {
                    return true;
                }
                counts[ch - 'a']++; // backtrack, this placement led nowhere
            }
        }
        return false;
    }
}

TIME O(N!) WORST CASESPACE O(N)JAVA · TRAINING PACE · 33 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED