☕ DSA Java Articles

Topics › Recursion and Backtracking › Trying out all Combos / Hard

Permutations of a String

Medium TUF ID 821 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a string s. Return all of its permutations: every string that uses each character of s exactly once, in some order. In the classic version (the SDE sheet entry, which LeetCode 46 poses on an array of distinct integers) all characters are distinct, so there are exactly n! answers. If a character repeats, two different orderings of the positions can spell the same string; each distinct string must appear once (LeetCode 47, “Permutations II”). The answers may be returned in any order.

Constraints: 0 ≤ n ≤ 8. The output alone holds up to n! · n characters, so n is always small: at n = 8 there are already 40,320 permutations, and at n = 12 there would be 479 million.

Example 1

s = "abc"
answer = [abc, acb, bac, bca, cab, cba]     // 3! = 6 arrangements of three distinct letters

Example 2

s = "aab"
answer = [aab, aba, baa]                    // 3! / 2! = 3; swapping the two a's creates nothing new

Approach 1: Brute force, pick any unused character

Intuition. Build the permutation one position at a time. The first position can hold any of the n characters, the second any of the n - 1 that remain, and so on. Recursion mirrors this exactly: keep a used flag for every index and a partial string cur. At each level, loop over all indices, take one that is not used yet, recurse, and then undo the choice so the next iteration starts from the same state. When cur reaches length n, every index has been used exactly once, so cur is a permutation.

Because the choice is made by index, not by value, a repeated letter produces the same string several times: in "aab", taking the first a then the second gives the same text as taking them the other way round. The brute force simply collects results in a set, which is correct but wasteful. For "aaaaaaa" it builds 5,040 strings to keep one.

Algorithm.

  1. Allocate used[n], an empty StringBuilder cur and an empty set found.
  2. build(): if cur.length() == n, add cur.toString() to found and return.
  3. For each index i with used[i] == false: mark it, append chars[i], call build(), then delete the last character and clear used[i].
  4. Return the contents of found as a list.
static List<String> bruteForce(String s) {
    Set<String> found = new LinkedHashSet<>();           // keeps generation order, drops duplicate arrangements
    build(s.toCharArray(), new boolean[s.length()], new StringBuilder(), found);
    return new ArrayList<>(found);
}

private static void build(char[] chars, boolean[] used, StringBuilder cur, Set<String> found) {
    if (cur.length() == chars.length) {                  // every character placed exactly once
        found.add(cur.toString());
        return;
    }
    for (int i = 0; i < chars.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        cur.append(chars[i]);
        build(chars, used, cur, found);
        cur.deleteCharAt(cur.length() - 1);              // undo: free the slot and the character
        used[i] = false;
    }
}

Complexity. Time O(n · n!). The recursion tree has n! / (n - k)! nodes at depth k; summed over all depths that is less than e · n! nodes, and each node runs a loop of n steps. Each of the n! leaves also spends O(n) to copy and hash its string. Space O(n) for used, cur and the recursion stack, on top of the O(n · n!) output (and the set that mirrors it).

Two details carry the whole method. cur.toString() makes a copy; adding the builder itself would store n! references to one object that ends up empty. And the undo lines must reverse the do lines exactly, in the opposite order, or the next loop iteration sees a corrupted state.

Approach 2: Better, swap characters into place

Intuition. The used array and the separate buffer can both disappear if the array keeps an invariant: positions 0 .. index-1 are already fixed, and a[index .. n-1] holds exactly the characters that are still free. To decide what goes at position index, swap each candidate a[i] with i ≥ index into that position, recurse on index + 1, then swap it back. Every call leaves the array exactly as it found it (each swap is undone before returning), so after the recursive call the suffix is restored and the next candidate is chosen from the same free set.

This structure also fixes duplicates at the source instead of after the fact. If two equal values are placed at the same position, the remaining free characters form the same multiset, so the two subtrees produce identical strings. A small set tried, local to each call, skips a value that has already been placed at index. Now any two leaves first differ at some position where they hold different values, so every output is distinct and no global set is needed. Nothing is lost either: every distinct free value is still tried at every position.

Algorithm.

  1. permuteBySwapping(a, index): if index == n, add new String(a) to the output and return.
  2. Create an empty set tried.
  3. For i from index to n - 1: if a[i] is already in tried, skip it; otherwise add it, swap a[index] and a[i], recurse with index + 1, and swap them back.
static List<String> better(String s) {
    List<String> out = new ArrayList<>();
    permuteBySwapping(s.toCharArray(), 0, out);
    return out;
}

private static void permuteBySwapping(char[] a, int index, List<String> out) {
    if (index == a.length) {                             // positions 0..n-1 are all fixed
        out.add(new String(a));
        return;
    }
    Set<Character> tried = new HashSet<>();              // values already placed at position `index`
    for (int i = index; i < a.length; i++) {
        if (!tried.add(a[i])) continue;                  // same value here would repeat a whole subtree
        swap(a, index, i);
        permuteBySwapping(a, index + 1, out);
        swap(a, index, i);                               // restore so the next candidate sees the same suffix
    }
}

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

Complexity. Time O(n · n!) for distinct characters: it is the same tree shape as Approach 1, with the loop now running over the n - index free positions only. With repeats the tree contains only distinct prefixes. There are at most P of them at each depth, where P is the number of distinct permutations, so the work is O(n² · P) at worst, and for "aaaaaaa" the whole tree is a single path. Space O(n) recursion depth plus the tried sets along the current path (at most n - index entries at depth index), besides the output.

The output order is not lexicographic. For "abc" the swaps produce abc, acb, bac, bca, cba, cab: the last two appear in that order because the third branch starts from cba after swapping a and c. If sorted output is required, Approach 3 gives it for free.

Approach 3: Optimal, iterate with next permutation

Intuition. Order all distinct arrangements lexicographically. Every arrangement except the largest has a unique successor, and it can be computed in place in O(n) without recursion. So start from the sorted string, which is the smallest arrangement, emit it, step to its successor, and repeat until the current string is the largest one (characters in non-increasing order). No recursion, no hash set, and the output comes out sorted.

Computing the successor:

  1. Find the rightmost i with a[i] < a[i + 1]. Everything to the right of i is non-increasing, which means it is already the largest possible arrangement of those characters. Nothing confined to that suffix can make the string bigger, so position i has to change. If no such i exists, the whole string is non-increasing and this was the last permutation.
  2. Find the rightmost j > i with a[j] > a[i]. Because the suffix is non-increasing, this is the smallest character in the suffix that is still bigger than a[i]. Swap a[i] and a[j]: the string grows by the smallest possible amount at position i.
  3. The suffix is still non-increasing after the swap. Reverse it so it becomes ascending, the smallest arrangement of those characters.

Duplicates need no special care. The strict comparisons (>= while scanning for i, <= while scanning for j) guarantee a strictly larger character moves into position i, so each step yields a strictly larger string. Because it is the immediate successor, no distinct string is skipped, and none repeats.

static List<String> optimal(String s) {
    char[] a = s.toCharArray();
    Arrays.sort(a);                                      // the smallest arrangement comes first
    List<String> out = new ArrayList<>();
    do {
        out.add(new String(a));
    } while (nextPermutation(a));
    return out;
}

private static boolean nextPermutation(char[] a) {
    int i = a.length - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--;              // a[i+1..] is the longest non-increasing suffix
    if (i < 0) return false;                             // whole array non-increasing: this was the last one
    int j = a.length - 1;
    while (a[j] <= a[i]) j--;                            // rightmost character strictly bigger than a[i]
    swap(a, i, j);
    for (int lo = i + 1, hi = a.length - 1; lo < hi; lo++, hi--) swap(a, lo, hi);   // make the suffix ascending
    return true;
}

The swap helper is the one from Approach 2.

Dry run on Example 2, s = "aab" (already sorted):

current emitted i (rightmost a[i] < a[i+1]) j (rightmost a[j] > a[i]) after swap after reversing a[i+1..]
aab aab 1 (a < b) 2 (b) aba aba
aba aba 0 (a < b; b ≥ a at index 1) 1 (b; index 2 holds a, not bigger) baa baa
baa baa none     stop

Three strings for three distinct arrangements; the duplicate a never caused a repeat. On "abc" the same loop emits abc, acb, bac, bca, cab, cba, sorted.

Complexity. Time O(n · P + n log n), where P ≤ n! is the number of distinct permutations: each step scans and reverses at most n characters and copies n characters into a new string, and the initial sort is O(n log n). Space O(1) beyond the character array and the output: no recursion stack, no sets.

All three methods are O(n · n!) on distinct input, which is the size of the output and therefore unavoidable. The differences show up on repeated characters (Approach 1 still does n! work), in memory (sets and recursion versus none), and in the order of the answer.

Edge cases and pitfalls