Recursive String Permutations

"Generate all permutations of a string." This classic interview question, also known as Permutations, is one of the most effective ways to test recursive thinking. It forces you to decompose a problem into smaller subproblems, handle a base case, and combine results back together. Companies like Google, Facebook, and Twitter use it to gauge how naturally you think in recursive terms.

TL;DR

Extract the first character, recursively permute the remaining string, then insert the first character at every position in each sub-permutation. The base case is an empty string returning an empty set. A single-character string returns a set containing just that character.

Why This Problem Matters

String permutations sit at the intersection of recursion, string manipulation, and combinatorics. Solving it well demonstrates that you can break a complex problem into smaller pieces and trust the recursive leap of faith. It also sets up your understanding of backtracking, which powers harder problems like N-Queens and Sudoku solvers.

Understanding the Problem

Given a string of unique characters, return a set containing every possible rearrangement of those characters.

permutations("") -> []
permutations("A") -> ["A"]
permutations("AB") -> ["AB", "BA"]
permutations("ABC") -> ["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"]

Since the output is a set, the ordering of the strings does not matter.

Constraints

• Use recursion and backtracking to solve this problem.
• 1 is less than or equal to n, and n is less than or equal to 15, where n is the length of the input string.
• All characters in the input string are unique.

Edge Cases

1. Empty string: Return an empty set (no characters to permute)
2. Single character: Return a set with just that character
3. Two characters: Return two permutations (the string and its reverse)

The Recursive Insight

The key observation connects to factorials. We know that n! = n * (n-1)!. In the same way, the permutations of an n-character string can be built from the permutations of the remaining (n-1) characters by inserting the extracted character at every possible position.

Here is the algorithm for input "ABC":

1. Extract the first character: first = 'A', remainder = "BC"
2. Recursively find permutations of "BC": {"BC", "CB"}
3. Insert 'A' at every position in "BC": "ABC", "BAC", "BCA"
4. Insert 'A' at every position in "CB": "ACB", "CAB", "CBA"
5. Combine all results: {"ABC", "ACB", "BAC", "BCA", "CAB", "CBA"}

Visualizing the Recursion

Let's trace the recursive calls for permutations("ABC"). Each call extracts the first character and recurses on the remainder until hitting the empty string base case:

Once the base case returns, the results bubble back up. The insertChar helper does the work of placing a character at every position in a word:

With the permutations of "BC" in hand ({"BC", "CB"}), we insert 'A' into each one to build the final result:

Solution Approach

The solution has two parts:

1. permutations(str): The main recursive method that splits the string and combines results.
2. insertChar(c, word): A helper that inserts a character at every position in a word.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;

public class Solution {
  public Set<String> permutations(String str) {
    if (str.isEmpty()) return new HashSet<>();
    else {
      char first = str.charAt(0);
      String remainder = str.substring(1);
      Set<String> remainderPermutations = permutations(remainder);
      if (remainderPermutations.isEmpty()) return Set.of(String.valueOf(first));
      return remainderPermutations
               .stream()
               .flatMap(word -> insertChar(first, word).stream())
               .collect(Collectors.toSet());
    }
  }

  private Set<String> insertChar(char c, String word) {
    Set<String> out = new HashSet<>();
    for (int i = 0; i <= word.length(); i++) {
      String left = word.substring(0, i);
      String right = word.substring(i);
      out.add(left + c + right);
    }
    return out;
  }
}

Step-by-Step Walkthrough

1. Base case: If the string is empty, return an empty set. This is the terminating condition.
2. Split: Extract the first character (first) and the remaining string (remainder).
3. Recurse: Call permutations(remainder) to get all permutations of the shorter string.
4. Single character: If the recursive result is empty (meaning we had a single character), return a set containing just that character.
5. Combine: For each permutation of the remainder, call insertChar to place first at every valid position. Use flatMap to flatten the nested sets into a single stream, then collect into a Set.

The insertChar helper iterates from index 0 to word.length(), splitting the word at each index and sandwiching the character in between. For a word of length k, this produces k+1 new strings.

Complexity Analysis

Time: O(n * n!). There are n! permutations of n unique characters. For each permutation, insertChar performs O(n) work (iterating through positions and creating substrings). The total work is O(n * n!).

Space: O(n!). The result set contains n! permutations. The recursion call stack goes n levels deep, but O(n!) dominates. Each permutation is a string of length n, so the total memory for results is O(n * n!).

Why Factorial Growth?

For a 3-character string, there are 3! = 6 permutations. For 10 characters, there are 3,628,800. For the maximum constraint of n=15, there are over 1.3 trillion permutations. This growth is inherent to the problem, not an inefficiency in the algorithm. Any correct solution must produce all n! results.

Common Pitfalls

1. Forgetting the single-character case: When the recursive call returns an empty set (the remainder was empty), you need to return a set with just the first character. Without this, a single-character input would incorrectly return an empty set.

2. Off-by-one in insertChar: The loop must go from 0 to word.length() inclusive. Missing the last position means you never place the character at the end of the word.

3. Using a list instead of a set: While the problem guarantees unique characters (so no duplicates are generated), returning a Set makes the contract explicit and matches the problem requirements.

4. Mutating strings during recursion: In languages where strings are mutable, be careful not to modify the input string. Always work with copies or substrings.

Interview Tips

When presenting this solution:

• Start by explaining the recursive decomposition: "I'll extract one character, permute the rest, then insert the extracted character everywhere."
• Draw out the recursion for a small input like "AB" or "ABC" to show how results build up.
• Mention the factorial time complexity and explain that it is optimal since any correct solution must enumerate all n! permutations.
• If asked about duplicates, explain that using a Set handles them, and note that the problem guarantees unique characters.

Key Takeaways

• String permutations decompose naturally via recursion: extract one character, permute the rest, insert everywhere.
• The insertChar helper is the workhorse that builds longer permutations from shorter ones by placing a character at every valid index.
• Time complexity is O(n * n!) and space is O(n!), both driven by the factorial number of permutations.
• The base case (empty string returns empty set) and the single-character case (return set of that character) are both critical for correctness.
• This pattern of "choose, recurse, combine" appears throughout recursion and backtracking problems.

Practice and Related Problems

Once you have string permutations down, explore these related challenges:

• Subset generation (power set) uses a similar recursive decomposition
• Combination sum applies the choose/recurse/combine pattern with constraints
• N-Queens extends backtracking to a 2D constraint satisfaction problem

This problem and hundreds of others are available on Firecode, where spaced repetition ensures you internalize patterns like recursion and backtracking rather than just memorizing solutions. Building recursive thinking here pays dividends across your entire interview preparation.

Solutions in Other Languages

Python

from typing import List, Set


class Solution:
    def permutations(self, s: str) -> Set[str]:
        if len(s) == 0:
            return set()
        else:
            first, remainder = s[0], s[1:]
            remainder_permutations: Set[str] = self.permutations(remainder)
            if len(remainder_permutations) == 0:
                return set(first)
            return set([item for
                        sublist in
                        [self.insert_char(first, w) for w in remainder_permutations]
                        for item in sublist])

    def insert_char(self, c: str, word: str) -> List[str]:
        out = []
        for i in range(0, len(word) + 1):
            left, right = word[0:i], word[i:]
            out.append(left + c + right)
        return out

JavaScript

class Solution {
  permutations(str) {
    if (str.length === 0) return new Set();
    else {
      const first = str.charAt(0);
      const remainder = str.substring(1);
      const remainderPermutations = this.permutations(remainder);
      if (remainderPermutations.size === 0) return new Set(first);
      return new Set([...remainderPermutations].flatMap(word => this.insertChar(first, word)));
    }
  }

  insertChar(c, word) {
    const out = [];
    for (let i = 0; i <= word.length; i++) {
      const left = word.substring(0, i);
      const right = word.substring(i);
      out.push(left + c + right);
    }
    return out;
  }
}

module.exports = Solution;

TypeScript

class Solution {
  permutations(str: string): Set<string> {
    if (str.length === 0) return new Set();
    else {
      const first = str.charAt(0);
      const remainder = str.substring(1);
      const remainderPermutations = this.permutations(remainder);
      if (remainderPermutations.size === 0) return new Set([first]);
      return new Set([...remainderPermutations].flatMap(word => this.insertChar(first, word)));
    }
  }

  private insertChar(c: string, word: string): string[] {
    const out: string[] = [];
    for (let i = 0; i <= word.length; i++) {
      const left = word.substring(0, i);
      const right = word.substring(i);
      out.push(left + c + right);
    }
    return out;
  }
}

C++

#include <iostream>
#include <unordered_set>

class Solution {
public:
  std::unordered_set<std::string> permutations(const std::string &str) {
    if (str.empty()) {
      return {};
    }
    char first = str[0];
    std::string remainder = str.substr(1);
    std::unordered_set<std::string> remainderPermutations = permutations(remainder);
    if (remainderPermutations.empty()) {
      return {std::string(1, first)};
    }
    std::unordered_set<std::string> result;
    for (const auto &word: remainderPermutations) {
      for (const auto &newWord: insertChar(first, word)) {
        result.insert(newWord);
      }
    }
    return result;
  }

private:
  std::vector<std::string> insertChar(char c, const std::string &word) {
    std::vector<std::string> out;
    for (size_t i = 0; i <= word.size(); ++i) {
      std::string left = word.substr(0, i);
      std::string right = word.substr(i);
      out.push_back(left + c + right);
    }
    return out;
  }
};

Go

package solution

func (s *Solution) Permutations(str string) map[string]bool {
	if len(str) == 0 {
		return make(map[string]bool)
	}

	first, remainder := string(str[0]), str[1:]
	remainderPermutations := s.Permutations(remainder)

	if len(remainderPermutations) == 0 {
		return map[string]bool{first: true}
	}

	result := make(map[string]bool)
	for word := range remainderPermutations {
		for _, newWord := range insertChar(first, word) {
			result[newWord] = true
		}
	}

	return result
}

func insertChar(c string, word string) []string {
	var out []string
	for i := 0; i <= len(word); i++ {
		left := word[:i]
		right := word[i:]
		out = append(out, left+c+right)
	}
	return out
}

type Solution struct {
}

Scala

import scala.collection.mutable

class Solution {
  def permutations(str: String): Set[String] = {
    if (str.isEmpty) Set.empty[String]
    else {
      val first = str.charAt(0)
      val remainder = str.substring(1)
      val remainderPermutations: Set[String] = permutations(remainder)
      if (remainderPermutations.isEmpty) return Set(first.toString)
      remainderPermutations.flatMap(insertChar(first, _))
    }
  }

  private def insertChar(c: Char, word: String): Set[String] = {
    val out = mutable.Set[String]()
    for (i <- 0 to word.length) {
      val left = word.substring(0, i)
      val right = word.substring(i)
      out.add(left + c + right)
    }
    out.toSet
  }
}

Kotlin

class Solution {
    fun permutations(str: String): Set<String> {
        if (str.isEmpty()) return emptySet()
        else {
            val first = str[0]
            val remainder = str.substring(1)
            val remainderPermutations = permutations(remainder)
            if (remainderPermutations.isEmpty()) return setOf(first.toString())
            return remainderPermutations
                    .flatMap { word -> insertChar(first, word) }
                    .toSet()
        }
    }

    private fun insertChar(c: Char, word: String): Set<String> {
        val out = mutableSetOf<String>()
        for (i in 0..word.length) {
            val left = word.substring(0, i)
            val right = word.substring(i)
            out.add(left + c + right)
        }
        return out
    }
}

Swift

class Solution {
    func permutations(_ str: String) -> Set<String> {
        if str.isEmpty { return Set<String>() }
        else {
            let first = str[str.startIndex]
            let remainder = String(str.dropFirst())
            let remainderPermutations = permutations(remainder)
            if remainderPermutations.isEmpty { return Set([String(first)]) }
            return Set(remainderPermutations.flatMap { word in insertChar(first, word) })
        }
    }

    private func insertChar(_ c: Character, _ word: String) -> Set<String> {
        var out = Set<String>()
        for i in 0...word.count {
            let left = String(word.prefix(i))
            let right = String(word.dropFirst(i))
            out.insert(left + String(c) + right)
        }
        return out
    }
}

Rust

impl Solution {
    pub fn permutations(&self, s: String) -> HashSet<String> {
        if s.is_empty() {
            return HashSet::new();
        }
        let first = s.chars().next().unwrap();
        let remainder: String = s.chars().skip(1).collect();
        let remainder_permutations = self.permutations(remainder);
        if remainder_permutations.is_empty() {
            let mut result = HashSet::new();
            result.insert(first.to_string());
            return result;
        }
        remainder_permutations
            .into_iter()
            .flat_map(|word| self.insert_char(first, &word))
            .collect()
    }

    fn insert_char(&self, c: char, word: &str) -> HashSet<String> {
        let mut out = HashSet::new();
        for i in 0..=word.len() {
            let mut new_word = String::from(&word[..i]);
            new_word.push(c);
            new_word.push_str(&word[i..]);
            out.insert(new_word);
        }
        out
    }
}

C#

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public HashSet<string> Permutations(string str) {
        if (str.Length == 0) return new HashSet<string>();
        else {
            char first = str[0];
            string remainder = str.Substring(1);
            var remainderPermutations = Permutations(remainder);
            if (remainderPermutations.Count == 0) return new HashSet<string> { first.ToString() };
            return new HashSet<string>(
                remainderPermutations
                    .SelectMany(word => InsertChar(first, word))
            );
        }
    }

    private HashSet<string> InsertChar(char c, string word) {
        var output = new HashSet<string>();
        for (int i = 0; i <= word.Length; i++) {
            string left = word.Substring(0, i);
            string right = word.Substring(i);
            output.Add(left + c + right);
        }
        return output;
    }
}

Dart

class Solution {
  Set<String> permutations(String str) {
    if (str.isEmpty) return {};
    else {
      String first = str[0];
      String remainder = str.substring(1);
      Set<String> remainderPermutations = permutations(remainder);
      if (remainderPermutations.isEmpty) return {first};
      return remainderPermutations
          .expand((word) => _insertChar(first, word))
          .toSet();
    }
  }

  Set<String> _insertChar(String c, String word) {
    Set<String> out = {};
    for (int i = 0; i <= word.length; i++) {
      String left = word.substring(0, i);
      String right = word.substring(i);
      out.add(left + c + right);
    }
    return out;
  }
}

PHP

<?php

class Solution {
    public function permutations(string $str): array {
        if (strlen($str) === 0) return [];
        $first = $str[0];
        $remainder = substr($str, 1);
        $remainderPermutations = $this->permutations($remainder);
        if (empty($remainderPermutations)) return [$first];
        return array_values(array_unique(
            array_merge(...array_map(fn($word) => $this->insertChar($first, $word), $remainderPermutations))
        ));
    }

    private function insertChar(string $c, string $word): array {
        $out = [];
        for ($i = 0; $i <= strlen($word); $i++) {
            $left = substr($word, 0, $i);
            $right = substr($word, $i);
            $out[] = $left . $c . $right;
        }
        return $out;
    }
}

Ruby

require 'set'

class Solution
  def permutations(str)
    return Set.new if str.empty?

    first = str[0]
    remainder = str[1..]
    remainder_permutations = permutations(remainder)
    return Set[first] if remainder_permutations.empty?
    remainder_permutations.flat_map { |word| insert_char(first, word) }.to_set
  end

  def insert_char(c, word)
    out = []
    (0..word.length).each do |i|
      left = word[0...i]
      right = word[i..]
      out << left + c + right
    end
    out
  end
end