Print all permutations of a string

The problem, simply

You get a string. Give back every order its letters can stand in. Each letter is used exactly once in each order. For n different letters there are n! orders: n choices for the first spot, n - 1 for the second, and so on.

A story to remember it

Picture it

Examples

Way 1: the simple way

Make every string of length n where each spot can be any letter, even a repeated one. Then keep only the strings that use each letter exactly once.

1. Fill spot 0 with each letter, then spot 1 with each letter, and so on, n levels deep.
2. When the string is full, count how often each letter was used. If every letter was used once, keep it.

import java.util.*;

class Solution {
    public List<String> permutations(String s) {
        List<String> result = new ArrayList<>();
        fill(s, new char[s.length()], 0, result);
        return result;
    }

    private void fill(String s, char[] cur, int spot, List<String> result) {
        if (spot == s.length()) {
            if (usesEachOnce(s, cur)) result.add(new String(cur));
            return;
        }
        for (int i = 0; i < s.length(); i++) {   // any letter, even one already used
            cur[spot] = s.charAt(i);
            fill(s, cur, spot + 1, result);
        }
    }

    private boolean usesEachOnce(String s, char[] cur) {
        int[] count = new int[128];
        for (char c : s.toCharArray()) count[c]++;
        for (char c : cur) if (--count[c] < 0) return false;
        return true;
    }
}

How long it takes: n^n strings, each checked in O(n), so O(n^n * n). For 8 letters that is about 16 million strings to find 40320 answers. Extra room: the current string and the call stack, O(n).

Way 2: the clever way

Never put a used letter in the first place. Keep a mark for each letter that is already standing in the row.

1. If all spots are full, the current order is an answer.
2. Otherwise, for each letter that is not marked: mark it, add it, fill the next spot.
3. Then remove it and unmark it. This undo lets the same letter stand somewhere else in a later order.

import java.util.*;

class Solution {
    public List<String> permutations(String s) {
        List<String> result = new ArrayList<>();
        build(s, new StringBuilder(), new boolean[s.length()], result);
        return result;
    }

    private void build(String s, StringBuilder cur, boolean[] used, List<String> result) {
        if (cur.length() == s.length()) {
            result.add(cur.toString());            // the row is full
            return;
        }
        for (int i = 0; i < s.length(); i++) {
            if (used[i]) continue;                 // already standing in the row
            used[i] = true;
            cur.append(s.charAt(i));
            build(s, cur, used, result);
            cur.deleteCharAt(cur.length() - 1);    // step out of the row
            used[i] = false;
        }
    }
}

How long it takes: there are n! answers, and each one costs O(n) to copy, so O(n * n!). You cannot do better, because just writing the answers takes that long. Extra room: the marks, the current order and the call stack, O(n), not counting the answers.

Another way: swapping in place

Instead of marks, keep the letters in an array. For spot i, swap each letter from i to the end into spot i, fill spot i + 1, then swap back.

import java.util.*;

class Solution {
    public List<String> permutations(String s) {
        List<String> result = new ArrayList<>();
        permute(s.toCharArray(), 0, result);
        return result;
    }

    private void permute(char[] a, int i, List<String> result) {
        if (i == a.length) {
            result.add(new String(a));
            return;
        }
        Set<Character> tried = new HashSet<>();    // skip a letter value already tried at this spot
        for (int j = i; j < a.length; j++) {
            if (!tried.add(a[j])) continue;
            swap(a, i, j);
            permute(a, i + 1, result);
            swap(a, i, j);                         // swap back
        }
    }

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

Same O(n * n!) time, no marks array. The tried set also removes repeats for words like AAB. One catch: the swap method does not list the orders in dictionary order. For ABC it gives ABC, ACB, BAC, BCA, CBA, CAB.

Watch out for

• Forgetting to unmark. Then after the first answer, no letter is free and the search stops early.
• Building a new string with + at every level. It works but copies a lot. A StringBuilder with add and remove is cheaper.
• Expecting dictionary order from the swap method. If order matters, sort first and use Way 2.

What interviewers ask next

• Print them in dictionary order without recursion. Sort, then repeat "next permutation": from the right, find the first letter smaller than the one after it, swap it with the smallest bigger letter to its right, and reverse the tail.
• Only the k-th order. Do not build them all. Divide k - 1 by (n - 1)! to pick the first letter, and repeat on the rest.
• How many different orders for a word with repeats? n! divided by c! for each letter that appears c times. AAB has 3! / 2! = 3.
• Permutations of an array of numbers instead of letters. Same code with a List<Integer>.

Remember this

Grown-up words: the orders are permutations, the marks are a visited array, the drawing is the recursion tree with n! leaves, and stepping out of the row is backtracking.