Leetcode reorganize strings

The problem, simply

You get a string s. Rearrange its letters so that no two neighbors are the same letter. Return any arrangement that works, or "" if none exists. This is LeetCode 767, Reorganize String.

For "aab" the answer is "aba". For "aaab" there is no way, so the answer is "".

A story to remember it

Picture it

Examples

Way 1: the simple way

Try to build the answer one spot at a time. At each spot, try every letter that still has copies left and is not the same as the letter just placed. If you get stuck, step back and try another letter.

1. Count each letter.
2. Fill spot pos: for each letter with count above 0 that differs from the previous letter, place it, lower its count, and fill pos + 1.
3. If a full string is built, return it. If every choice fails, undo and return failure.

class Solution {
    public String reorganizeString(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        char[] out = new char[s.length()];
        return fill(out, 0, count) ? new String(out) : "";
    }

    private boolean fill(char[] out, int pos, int[] count) {
        if (pos == out.length) return true;
        for (int c = 0; c < 26; c++) {
            if (count[c] == 0) continue;
            if (pos > 0 && out[pos - 1] == (char) ('a' + c)) continue; // same as neighbor
            out[pos] = (char) ('a' + c);
            count[c]--;
            if (fill(out, pos + 1, count)) return true;
            count[c]++;                                               // undo and try another
        }
        return false;
    }
}

How long it takes: in the worst case it tries a huge number of orders, up to about n!, and checks each in O(n). Impossible inputs like "aaaaaaaaaabbbb" make it explore a lot before giving up. Extra room: the recursion, O(n).

Way 2: the clever way

Do what the teacher does. Keep (count, letter) pairs in a max heap ordered by count.

1. Count each letter. If any count is more than (n + 1) / 2, return "".
2. While the heap has at least two pairs:
   • Poll the two biggest pairs. They are different letters, so write both.
   • Lower both counts by one, and put back any pair that still has a count above 0.
3. If one pair is left, it has count 1. Write its letter.

import java.util.PriorityQueue;

class Solution {
    public String reorganizeString(String s) {
        int n = s.length();
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;

        // {count, letter}, biggest count on top
        PriorityQueue<int[]> heap = new PriorityQueue<>((x, y) -> Integer.compare(y[0], x[0]));
        for (int c = 0; c < 26; c++) {
            if (count[c] > (n + 1) / 2) return "";      // too many of one letter
            if (count[c] > 0) heap.offer(new int[] { count[c], c });
        }

        StringBuilder out = new StringBuilder();
        while (heap.size() >= 2) {
            int[] first = heap.poll();
            int[] second = heap.poll();
            out.append((char) ('a' + first[1]));
            out.append((char) ('a' + second[1]));        // two different letters
            if (--first[0] > 0) heap.offer(first);
            if (--second[0] > 0) heap.offer(second);
        }
        if (!heap.isEmpty()) out.append((char) ('a' + heap.poll()[1])); // count is 1 here
        return out.toString();
    }
}

How long it takes: n letters are written and each costs O(log k) on a heap of k different letters, so O(n log k). With only 26 letters that is really O(n). Extra room: the heap, O(k).

Another way: fill the even spots first

There is an O(n) trick with no heap. Put the most common letter on spots 0, 2, 4, and so on. Then keep filling the remaining even spots, and after the end wrap to spots 1, 3, 5, with every other letter. Equal letters always land two spots apart, so they never touch.

class Solution {
    public String reorganizeString(String s) {
        int n = s.length();
        int[] count = new int[26];
        int most = 0;
        for (char c : s.toCharArray()) {
            if (++count[c - 'a'] > count[most]) most = c - 'a';
        }
        if (count[most] > (n + 1) / 2) return "";
        char[] out = new char[n];
        int pos = 0;
        while (count[most] > 0) {                 // the most common letter first
            out[pos] = (char) ('a' + most);
            pos += 2;
            count[most]--;
        }
        for (int c = 0; c < 26; c++) {
            while (count[c] > 0) {
                if (pos >= n) pos = 1;            // even spots are full, switch to odd
                out[pos] = (char) ('a' + c);
                pos += 2;
                count[c]--;
            }
        }
        return new String(out);
    }
}

Watch out for

• The limit is (n + 1) / 2 with integer division. For n = 5, a letter may appear 3 times (a?a?a).
• Check the limit before you start, or check at the end that the answer has length n.
• Compare counts with Integer.compare. Ties are fine: any order works.
• In the even spots trick, the most common letter must go first. If another letter takes the first even spots, the most common one can be pushed onto two neighboring spots after the wrap.

What interviewers ask next

• Equal letters must be at least k apart (LeetCode 358)? Use the heap, but put each used letter in a waiting line for k turns before it can go back into the heap.
• Task scheduler with a cooldown (LeetCode 621)? Same counting. The answer is max(n, (maxCount - 1) * (k + 1) + numberOfLettersWithMaxCount).
• Why is (n + 1) / 2 the exact limit? Put the most common letter on every other spot starting at spot 0. That fits (n + 1) / 2 copies and no more, and the other letters can fill the gaps.
• Longest happy string with at most two equal letters in a row (LeetCode 1405)? A max heap of counts, and skip the top when it would make three in a row.

Remember this

Grown-up words: the families are letter frequencies, the line of biggest families is a max heap (priority queue), picking the biggest first is a greedy choice, and the more than half rule is the feasibility check maxCount <= (n + 1) / 2.