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

Solution: Permutations

Explore how to generate all permutations of a given string by applying the subsets pattern and recursive depth-first search. This lesson guides you through fixing characters, swapping indices, and recursively computing permutations, enabling you to systematically explore all arrangements. You'll understand the approach, implement the solution in Python, and analyze its time and space complexity.

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