Reorganize String

NeetCode: Reorganize String · LeetCode: 767. Reorganize String · Difficulty: Medium

Given a string s of lowercase letters, rearrange its characters so that no two adjacent characters are the same. Return any valid rearrangement, or the empty string if none exists.

Example

Text

Input:  s = "aab"    Output: "aba"
Input:  s = "aaab"   Output: ""

Because any valid answer is accepted, the programs below print whether the returned string is a valid rearrangement rather than the string itself.

Brute force: backtracking

Build the answer one position at a time. At each position try every letter that still has a remaining count and differs from the previous letter; if the search gets stuck, undo the last choice and try the next letter. The StringBuilder is a mutable string buffer, so append and deleteCharAt add and undo a choice in place.

Java

import java.util.Arrays;

class Solution {
    public String reorganizeString(String s) {
        int[] counts = new int[26];
        for (int i = 0; i < s.length(); i++) {
            counts[s.charAt(i) - 'a']++;
        }
        StringBuilder out = new StringBuilder();
        return backtrack(counts, -1, out, s.length()) ? out.toString() : "";
    }

    private boolean backtrack(int[] counts, int prev, StringBuilder out, int n) {
        if (out.length() == n) {
            return true;
        }
        for (int c = 0; c < 26; c++) {
            if (counts[c] == 0 || c == prev) {
                continue;
            }
            counts[c]--;
            out.append((char) ('a' + c));
            if (backtrack(counts, c, out, n)) {
                return true;
            }
            out.deleteCharAt(out.length() - 1);
            counts[c]++;
        }
        return false;
    }
}

public class Main {
    static boolean isValid(String input, String out) {
        char[] a = input.toCharArray();
        char[] b = out.toCharArray();
        Arrays.sort(a);
        Arrays.sort(b);
        if (!Arrays.equals(a, b)) {
            return false;
        }
        for (int i = 1; i < out.length(); i++) {
            if (out.charAt(i) == out.charAt(i - 1)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        for (String s : new String[] {"aab", "aaab", "a", "aabbcc", "vvvlo"}) {
            String r = solution.reorganizeString(s);
            String verdict = r.isEmpty() ? "impossible" : isValid(s, r) ? "valid" : "WRONG";
            System.out.println(s + " -> " + verdict);
        }
    }
}

Output

aab -> valid
aaab -> impossible
a -> valid
aabbcc -> valid
vvvlo -> valid

With no pruning, an impossible input such as aaab forces the search to exhaust essentially every arrangement, which is factorial in the worst case (up to O(n!/(c1! c2! ...)) distinct arrangements). Even solvable inputs can backtrack a lot. Time: exponential in the worst case. Space: O(n) recursion depth.

Optimal: greedy with a max-heap

Two facts make this greedy:

A valid arrangement exists exactly when the most frequent letter appears at most (n + 1) / 2 times. Impossibility can therefore be decided up front.
Placing the currently most frequent letter (other than the one just placed) never leads to a dead end: the most frequent letter is the hardest to separate, so using it first is safe.

Keep a max-heap of (count, letter). PriorityQueue is a min-heap, so the comparator orders by larger count first. The comparator uses Integer.compare, not subtraction, which can overflow. Pop the top, append it, and hold it back for one step (it cannot go next). Push back the previously held letter if it still has copies. This is equivalent to popping two letters at a time, using a single held slot, which is null when empty.

Java

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public String reorganizeString(String s) {
        int n = s.length();
        int[] counts = new int[26];
        for (int i = 0; i < n; i++) {
            counts[s.charAt(i) - 'a']++;
        }
        for (int c : counts) {
            if (c > (n + 1) / 2) {
                return "";
            }
        }
        // Each entry is {count, letter index}; larger count first, then larger letter.
        PriorityQueue<int[]> heap = new PriorityQueue<>((x, y) ->
                x[0] != y[0] ? Integer.compare(y[0], x[0]) : Integer.compare(y[1], x[1]));
        for (int letter = 0; letter < 26; letter++) {
            if (counts[letter] > 0) {
                heap.add(new int[] {counts[letter], letter});
            }
        }
        StringBuilder out = new StringBuilder();
        int[] held = null;
        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            out.append((char) ('a' + top[1]));
            if (held != null) {
                heap.add(held);
                held = null;
            }
            if (top[0] > 1) {
                held = new int[] {top[0] - 1, top[1]};
            }
        }
        return out.toString();
    }
}

public class Main {
    static boolean isValid(String input, String out) {
        char[] a = input.toCharArray();
        char[] b = out.toCharArray();
        Arrays.sort(a);
        Arrays.sort(b);
        if (!Arrays.equals(a, b)) {
            return false;
        }
        for (int i = 1; i < out.length(); i++) {
            if (out.charAt(i) == out.charAt(i - 1)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        for (String s : new String[] {"aab", "aaab", "a", "aabbcc", "vvvlo"}) {
            String r = solution.reorganizeString(s);
            String verdict = r.isEmpty() ? "impossible" : isValid(s, r) ? "valid" : "WRONG";
            System.out.println(s + " -> " + verdict);
        }
    }
}

Output

aab -> valid
aaab -> impossible
a -> valid
aabbcc -> valid
vvvlo -> valid

Time: O(n log k) where k <= 26 is the number of distinct letters, so effectively O(n). Space: O(n) for the output; the heap holds at most 26 entries.