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

Solution: Permutations

Explore how to generate all permutations of a given string using the subsets pattern and a recursive depth-first search approach. Learn the step-by-step method to fix characters, swap indices, and recursively compute permutations. Understand the time and space complexity of this technique to solve coding interview problems effectively.

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 the ...