Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in Go

Solution: Permutations

Explore how to systematically generate all permutations of a given string with unique characters by applying the subsets pattern and Depth-First Search. Learn to implement recursive solutions that fix each character in turn and compute remaining permutations, understanding the time and space complexity involved.

We'll cover the following...

Statement

Given an input string, word, return all possible permutations of the string.

Note: The order of permutations does not matter.

Constraints:

  • All characters in word are unique.

  • 1≤1 \leq word.length ≤6\leq 6

  • All characters in word are lowercase English letters.

Pattern: Subsets

Problems such as this one, where we need to find the combinations or permutations of a given string, are good examples to solve using the subsets pattern as it describes an efficient Depth-First Search (DFS) approach to handle all these problems.

Solution

Let’s discuss a few basics first. We know that n!n! is the number of permutations for a set of size nn. Another obvious and important concept is that if we choose an element for the first position, then the total permutations of the remaining elements are (n−1)!(n-1)!.

For example, if we’re given the string “abcd” and we pick “a” as our first element, then for ...