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

Solution: Permutations

Explore how to solve permutations of a string with unique characters by applying the subsets pattern and recursive depth-first search. Understand the step-by-step approach of fixing characters, swapping, and recursively generating permutations. This lesson helps you grasp the use of recursion and backtracking to efficiently compute all permutations.

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