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 letters next to each other are the same. Give back any such string. If it cannot be done, give back an empty string "".

Below, n is the length and k is the number of different letters (at most 26).

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 two neighbors match. Make the orders with the swap method from "permutations of a string".

1. Swap a letter into spot i, then fill the rest the same way.
2. When the row is full, check every pair of neighbors.
3. Stop at the first good row. If none is good, return "".

class Solution {
    public String reorganizeString(String s) {
        char[] a = s.toCharArray();
        return tryAll(a, 0) ? new String(a) : "";
    }

    private boolean tryAll(char[] a, int i) {
        if (i == a.length) {
            for (int k = 1; k < a.length; k++) {
                if (a[k] == a[k - 1]) return false;   // twins side by side
            }
            return true;
        }
        for (int j = i; j < a.length; j++) {
            swap(a, i, j);
            if (tryAll(a, i + 1)) return true;
            swap(a, i, j);                            // undo
        }
        return false;
    }

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

How long it takes: up to n! orders, each checked in n steps, so O(n! * n). For 12 letters that is billions of steps. Extra room: the recursion, O(n).

Way 2: the clever way

Follow the party rule with a heap, a pile that always hands you the letter with the most copies left.

1. Count every letter. If one letter has more than (n + 1) / 2 copies, return "".
2. Put each letter and its count into a max heap.
3. While the heap has at least two letters: take the top two. They are different letters, so write the first, then the second.
4. Put each back with one fewer copy, if it has any left.
5. If one letter is left in the heap, it has exactly one copy. Write it at the end.

Taking two different letters each round means the round never starts with the letter that ended the round before. The check in step 1 makes sure the last leftover letter has only one copy.

import java.util.*;

class Solution {
    public String reorganizeString(String s) {
        int n = s.length();
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        for (int c : count) if (c > (n + 1) / 2) return "";   // too many twins

        // most copies first; on a tie, the earlier letter first
        PriorityQueue<int[]> heap = new PriorityQueue<>(
            (x, y) -> x[0] != y[0] ? y[0] - x[0] : x[1] - y[1]);
        for (int i = 0; i < 26; i++) if (count[i] > 0) heap.offer(new int[]{count[i], i});

        StringBuilder out = new StringBuilder();
        while (heap.size() >= 2) {
            int[] first = heap.poll(), second = heap.poll();
            out.append((char) ('a' + first[1])).append((char) ('a' + second[1]));
            if (--first[0] > 0) heap.offer(first);     // put back with one less
            if (--second[0] > 0) heap.offer(second);
        }
        if (!heap.isEmpty()) out.append((char) ('a' + heap.poll()[1]));
        return out.toString();
    }
}

How long it takes: every letter of the answer costs a heap step of O(log k), so O(n log k). With only 26 letters, that is O(n) in practice. Extra room: the heap holds at most k letters, O(k).

Way 3: fill the even spots first

There is an even faster trick. Put the most common letter on spots 0, 2, 4 and so on. Then pour every other letter into the remaining even spots, and when you run off the end, continue at spot 1, 3, 5. Copies of one letter 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 top = 0;
        for (char c : s.toCharArray()) {
            if (++count[c - 'a'] > count[top]) top = c - 'a';
        }
        if (count[top] > (n + 1) / 2) return "";

        char[] out = new char[n];
        int idx = 0;
        while (count[top] > 0) {              // the most common letter first
            out[idx] = (char) ('a' + top);
            idx += 2;
            count[top]--;
        }
        for (int i = 0; i < 26; i++) {
            while (count[i] > 0) {
                if (idx >= n) idx = 1;        // even spots are full, go to odd
                out[idx] = (char) ('a' + i);
                idx += 2;
                count[i]--;
            }
        }
        return new String(out);
    }
}

This runs in O(n) time with a 26 slot table, O(1) extra room besides the answer.

Watch out for

• The test is count > (n + 1) / 2, not count > n / 2. For n = 5, three copies are fine.
• In the heap, take both letters out before putting either back. Putting the first back right away may hand it to you again.
• Java's PriorityQueue is a min heap. Flip the comparator to get the most copies on top.
• The empty string is a valid answer for an empty input.

What interviewers ask next

• Same letters must be at least k apart (LeetCode 358)? Use the heap, but park each used letter in a waiting line for k turns before it can go back in the heap.
• Task scheduler (LeetCode 621): the least time to run tasks when equal tasks need a cooldown of k? The answer is max(n, (maxCount - 1) * (k + 1) + number of letters with maxCount).
• Can you prove the greedy always works when the count test passes? Spreading the most common letter first leaves the smallest chance of it getting stuck at the end. Way 3 shows it directly: copies sit two spots apart.
• Return the number of valid arrangements? That is counting with inclusion and exclusion or dynamic programming, a much harder problem.

Remember this

Grown-up words: the party rule is a greedy choice, the pile is a max heap (a priority queue), the counts are a frequency table, and the even spots trick is interleaving.