Rearrange characters in a string such that no two adjacent are same

The problem, simply

You get a string of lowercase letters. Rearrange its letters so that no two neighbours are the same letter. Give back any such string, or an empty string if it cannot be done.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every order of the letters and return the first one where no neighbours match.

class Solution {
    public String rearrange(String s) {
        char[] c = s.toCharArray();
        return tryOrders(c, 0) ? new String(c) : "";
    }

    private boolean tryOrders(char[] c, int start) {
        if (start == c.length) {
            for (int i = 1; i < c.length; i++) if (c[i] == c[i - 1]) return false;
            return true;                                  // no neighbours match
        }
        for (int i = start; i < c.length; i++) {
            swap(c, start, i);
            if (tryOrders(c, start + 1)) return true;
            swap(c, start, i);
        }
        return false;
    }

    private void swap(char[] c, int i, int j) { char t = c[i]; c[i] = c[j]; c[j] = t; }
}

How long it takes: up to n! orders, each checked in n steps, O(n! * n). Twelve letters is already 479 million orders. Extra room: the recursion, O(n).

Way 2: the clever way

The letter with the most copies left is the hardest to place, so place it as early as you can. The only thing stopping you is the letter you just wrote. So keep that letter aside for one turn.

1. Count each letter. If any count is more than (n + 1) / 2, return "". There are not enough other letters to separate its copies.
2. Put every letter with its count into a max-heap, ordered by count.
3. Repeat until the heap is empty: take the top letter, write it, lower its count. Put the letter that sat out last turn back into the heap if it still has copies. The letter you just wrote now sits out.

import java.util.*;

class Solution {
    public String rearrange(String s) {
        int n = s.length();
        int[] count = new int[26];
        for (char ch : s.toCharArray()) count[ch - 'a']++;
        for (int c : count) if (c > (n + 1) / 2) return "";      // cannot be separated
        // entries are {letter, copies left}: most copies first, then the earlier letter
        PriorityQueue<int[]> heap = new PriorityQueue<>((x, y) -> x[1] != y[1] ? y[1] - x[1] : x[0] - y[0]);
        for (int i = 0; i < 26; i++) if (count[i] > 0) heap.add(new int[]{i, count[i]});
        StringBuilder out = new StringBuilder();
        int[] sittingOut = null;                    // the letter written last turn
        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            out.append((char) ('a' + top[0]));
            top[1]--;
            if (sittingOut != null && sittingOut[1] > 0) heap.add(sittingOut);  // it may play again
            sittingOut = top;
        }
        return out.toString();
    }
}

How long it takes: n letters are written, and each step does a heap operation on at most k distinct letters, so O(n log k). With 26 letters that is really O(n). Extra room: the counts and the heap, O(k), plus the answer.

Watch out for

• The limit is (n + 1) / 2, not n / 2. For odd n the top letter can take one extra spot: 'aba' is fine.
• Check the limit first, or check at the end that the answer has length n. Without either, a bad input gives a short wrong answer.
• Ties in the heap can go either way. Any valid answer is accepted.

What interviewers ask next

• Can you do it in O(n) without a heap? Yes. Put the most common letter on positions 0, 2, 4 and so on. Then fill the remaining even positions and then the odd positions with the other letters, one letter at a time. Because the most common letter goes first, no two copies of any letter end up side by side.
• Equal letters must be at least k apart. Use the same heap, but keep the used letters in a waiting line of length k and release each one after k turns.
• Task scheduler: tasks with a cooldown of k and idle slots allowed. The answer is max(n, (maxCount - 1) * (k + 1) + number of letters with maxCount).
• Why does the greedy never get stuck when the limit holds? It always uses up the letter with the most copies, so no letter ever grows past half of the letters still left (rounded up). That means there is always a different letter to write next.

Remember this

Grown-up words: the teams are character counts, the pile with the biggest team on top is a max-heap or priority queue, sitting out one turn is a cooldown of 1, and the limit (n + 1) / 2 is the pigeonhole bound.