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

The problem, simply

You get a string. Rearrange its characters so that no two neighbors are equal. If that is impossible, return an empty string. Here n is the length and k is the number of different characters.

For "aaabc" one answer is "acaba". For "aaab" there is no answer.

A story to remember it

Picture it

Examples

Way 1: the simple way

Do the teacher's plan without a heap. At each step, look at every letter, and pick the one with the most copies left that is not the letter you just placed.

1. Count each letter.
2. For each of the n spots, scan all k letters for the biggest count that is not the previous letter.
3. If no letter can be picked, return "".

class Solution {
    public String rearrange(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        StringBuilder out = new StringBuilder();
        int prev = -1;
        for (int step = 0; step < s.length(); step++) {
            int pick = -1;
            for (int c = 0; c < 26; c++) {           // scan every letter
                if (c != prev && count[c] > 0 && (pick == -1 || count[c] > count[pick])) pick = c;
            }
            if (pick == -1) return "";               // only the previous letter is left
            out.append((char) ('a' + pick));
            count[pick]--;
            prev = pick;
        }
        return out.toString();
    }
}

How long it takes: n steps, each scanning k letters, O(n * k). With 26 letters that is fine, but with a big alphabet (all of Unicode, or numbers as "letters") the scan gets slow. Extra room: the counts, O(k).

Way 2: the clever way

Let a max heap find the biggest count, and keep the letter that just went on a bench for one turn.

1. Count each letter and put (count, letter) pairs in a max heap.
2. While the heap is not empty:
   • Poll the top pair and write its letter.
   • If the benched pair still has copies, put it back into the heap.
   • Bench the pair you just used, with its count lowered by one.
3. If the answer has all n letters, return it. If not, a letter got stuck on the bench, so return "".

When it fails, it fails like this:

import java.util.PriorityQueue;

class Solution {
    public String rearrange(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        PriorityQueue<int[]> heap = new PriorityQueue<>((x, y) -> Integer.compare(y[0], x[0])); // max heap
        for (int c = 0; c < 26; c++) {
            if (count[c] > 0) heap.offer(new int[] { count[c], c });
        }

        StringBuilder out = new StringBuilder();
        int[] bench = null;                          // the letter that just went
        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            out.append((char) ('a' + top[1]));
            if (bench != null && bench[0] > 0) heap.offer(bench); // back from the bench
            top[0]--;
            bench = top;                             // sits out one turn
        }
        return out.length() == s.length() ? out.toString() : "";
    }
}

How long it takes: each of the n letters costs one poll and at most one offer, O(n log k). Extra room: the heap, O(k).

Watch out for

• Do not forget the final check. When a letter is stuck on the bench, the loop ends with a short answer. Compare the length with n.
• You can also check up front: if the biggest count is more than (n + 1) / 2, return "" at once.
• A string of length 0 or 1 is already fine.
• Uppercase, digits or any characters? Use a HashMap<Character, Integer> for counts instead of a 26 slot array.

What interviewers ask next

• Equal characters must be at least d apart? Make the bench a waiting line that holds the last d - 1 used letters. A letter comes back to the heap only when it leaves the front of the line. This is the same code with a queue instead of one slot.
• Can it be O(n)? Yes. Put the most common letter on spots 0, 2, 4 and so on, then fill the rest of the even spots and then the odd spots with the other letters.
• How many arrangements exist? That is a counting problem with inclusion and exclusion, much harder. Interviewers usually stop at "find one".
• Task scheduler with idle slots? The same greedy, but instead of failing when everything is on the bench, you add an idle step.

Remember this

Grown-up words: the classes are character frequencies, the line of biggest classes is a max heap (priority queue), the bench is a cooldown slot (a queue when the gap is bigger than one), and always choosing the biggest class is a greedy choice.