Print all the permutations of the given string

The problem, simply

A permutation is the same letters in a new order. abc can become acb, bac, bca, cab or cba, and itself. Print all of them.

With n different letters there are n! orders: n choices for the first spot, n - 1 for the second, and so on. If letters repeat, like aab, print each different order only once.

A story to remember it

Picture it

Examples

Way 1: the simple way

For each of the n spots, try every position of the original string, even ones already used. That makes n^n fillings. At the end, keep only the fillings that used every position exactly once.

1. Fill spot 0 with any position 0..n-1, then spot 1, and so on.
2. When all spots are filled, check that no position was used twice.
3. If the check passes, build the word and keep it.

import java.util.*;

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

    private void fill(String s, int[] pick, int spot, List<String> out) {
        int n = s.length();
        if (spot == n) {
            boolean[] used = new boolean[n];
            StringBuilder word = new StringBuilder();
            for (int p : pick) {
                if (used[p]) return;          // a friend in two spots, throw it away
                used[p] = true;
                word.append(s.charAt(p));
            }
            out.add(word.toString());
            return;
        }
        for (int p = 0; p < n; p++) {
            pick[spot] = p;
            fill(s, pick, spot + 1, out);
        }
    }
}

How long it takes: n^n fillings, each checked in n steps, so O(n^n * n). For 8 letters that is 16 million fillings for only 40,320 real answers. Extra room: O(n). It also prints repeats for aab.

Way 2: the clever way

Never build a bad filling in the first place. Fill spot i only with letters that are still free. A neat way to keep track: the free letters are always the ones at positions i and after. So to put letter j in spot i, swap a[i] and a[j], solve the rest from i + 1, then swap them back.

To skip repeats, remember which letters you already tried in spot i. Trying a second a there would only make the same words again.

1. If i is the last spot (or past it), the row is finished. Print it.
2. For each j from i to the end: if a[j] was already tried in spot i, skip it.
3. Swap a[i] and a[j], recurse on i + 1, then swap back.

import java.util.*;

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

    private void permute(char[] a, int i, List<String> out) {
        if (i >= a.length - 1) {                 // zero or one spot left: done
            out.add(new String(a));
            return;
        }
        Set<Character> tried = new HashSet<>();  // letters already tried in spot i
        for (int j = i; j < a.length; j++) {
            if (!tried.add(a[j])) continue;      // same letter, same words, skip
            swap(a, i, j);                       // put a[j] in spot i
            permute(a, i + 1, out);
            swap(a, i, j);                       // undo
        }
    }

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

How long it takes: there are n! finished rows, and making each one into a string costs n, so O(n * n!). The tree above the leaves adds less than that. Extra room: the recursion is n levels deep, and each level keeps a small set, so O(n) besides the letters, not counting the answers.

Watch out for

• With repeated letters, a set of all answers works too, but it still makes all n! rows first. Skipping a letter already tried at this spot never makes the repeats at all.
• The swap method does not print in dictionary order (cba comes before cab). Sort first and use the "pick a free letter" method, or sort at the end, if order matters.
• n! grows very fast: 10 letters already give 3,628,800 orders.
• Another common way keeps a used[] array and a builder, and for each spot picks any unused letter. Same O(n * n!) time.

What interviewers ask next

• Print in dictionary order with repeats removed? Sort the letters, keep used[], and skip letter i when it equals letter i - 1 and letter i - 1 is not used right now.
• Next permutation in place? From the right, find the first a[i] < a[i + 1], swap a[i] with the smallest bigger letter to its right, then reverse everything after i. O(n).
• What is the kth permutation in order without listing them? Each first letter covers (n - 1)! permutations, so divide k by that to pick the first letter, and repeat.
• Is s2 holding some permutation of s1? Do not list them. Slide a window of length s1.length() over s2 with 26 letter counts.

Remember this

Grown-up words: the photo rows are permutations, the tree of choices is a recursion tree, swapping in and back out is backtracking, and n! is n factorial.