Solution: Permutations

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 \leq$ word.length $\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!$ is the number of permutations for a set of size $n$. 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)!$.

For example, if we’re given the string “abcd” and we pick “a” as our first element, then for the remaining elements we have the following permutations:

Similarly, if we pick “b” as the first element, permute “acd”, and prepend each permutation with “b”, we can observe a pattern here as shown in the illustration above. That pattern tells us how to find all remaining permutations for each character in the given string.

We can do this recursively to find all permutations of substrings, such as “bcd”, “acd”, and so on.

Here is a visual representation of all recursions for input string “bad”:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction#

Let’s start with the simplest step—swapping the indexes of the input string. We create a function to swap $i^{th}$ and $j^{th}$ indexes of a given string.

The next part of the solution construction consists of actually calculating the first permutation for the input string. After swapping, we need to find the permutations as well. Let’s see how we can implement this logic.

We create a recursive function to compute the permutations of the string that has been passed as input. The function behaves in the following way:

• We fix the first character of the input string and swap it with its immediate next character.

• We swap the indexes and get a new permutation of the string, which is stored in the variable, swapped_str.

• The recursive call for the function increments the index by adding $1$ to the current_index variable to compute the next permutation.

• All permutations of the string are stored in the result array, but for the following code snippet, only the base case—that is, only the first permutation—is displayed.

We first swapped the indexes and then displayed the first possible permutation of the input string, that is, the input string itself. Let’s update the functionality to compute and store all possible permutations.

To implement this logic, we’ve made a function that takes the string as input, calls the recursive function, permute_string_rec that computes all permutations (as done in the previous step), and finally stores and displays the result array containing the permutations.

Just the code#

Here’s the complete solution to this problem:

Solution summary#

Let’s review what approach we’ve used to solve the problem above:

1. Fix the first index and keep swapping the character at this index with the other characters of the string one by one.

2. After each swap, skip the first character and recursively compute the permutation of the remaining string.

3. Add the string to the result when the last character of the string is reached.

Time complexity#

Let’s anaylze the time complexity of the solution code above:

• permute_word(): There are $n!$ (factorial of $n$) permutations of a string of length $n$.
• permute_string_rec(): This is a recursive function that generates these permutations. For a string of length $n$, there are $n$ recursive calls at the first level, $n-1$ calls for the second, and so on. This results in a total of $n \times (n-1) \times (n-2) \times \dots \times 1 = n!$ calls.
• swap_char(): The swap function has a time complexity of $O(n)$ since it involves creating a list from the string and then joining it back into a string after the swap. This operation is done for each recursive call.

So, the overall time complexity of generating all permutations of a string of length $n$ is $O(n \times n!)$

Space complexity#

The space complexity of this solution is dependent on the depth of the recursive call stack. The maximum depth of recursion is $n$, so the space complexity is $O(n)$.