🧩 Objective

Write a recursive method for generating all permutations of an input string. Return them as a set.

See: Recursive String Permutations - Interview Cake

🔎 Questions

1: How does the problem change if the string can have duplicate characters?

• The solution below works with duplicate characters because the index of the original input is used to generate unique combinations of the original input minus the character at the given index. Therefore, there may be duplicate characters, however, their unique indexes will generate the correct solution.

2: What is the space and time complexity?

• Time Complexity: $$\O(n^2)\$$ because there is one iteration through the input for which index to examine, and a second iteration, placing the character at each position of the input to generate various combinations. Therefore, $$\n x n\$$. This follows the rule, do X for each time of Y. See: Time complexity of all permutations of a string - GeeksforGeeks

• Space Complexity: Is the space complexity also quadratic $$\O(n^2)\$$ because the unique permutations stored in a Set would grow quickly based on the size of the initial input?

3: How to optimize the time and space complexity?

• Time Complexity: I do not see further time complexity optimizations.

• Space Complexity: I do not see further space complexity optimizations because the solution syntactically is recursive, but performs iteratively. The recursive part of the code, allPerm performs after each iteration through the input. Therefore, there are no methods saved onto the JVM's call stack.

🚀 Code

1. Iterate through each char and move the char to each position of the input String.
2. Add each version to a Set.
fun allPerm(input: String, lookAtIndex: Int, set: HashSet<String>): HashSet<String> {
if (lookAtIndex <= input.length - 1) {
for (i in 0 .. input.length - 1) {
val combo = input.substring(0, lookAtIndex) +
input.substring(lookAtIndex + 1)
combo.substring(i))
}
allPerm(input, lookAtIndex + 1, set)
}
return set
}


See: GitHub

• Consider the input abcdefghijklmnopqrstuvwxyz and think about how many different combinations that will return. Then consider if this is more than, less than, or equal to O(n^2). Nov 2, 2020 at 22:20
• Also consider the input aaaaaaaaaaaaaaaaaaaaaa and think about how many different combinations that will return. Now consider if you can make any performance improvement. Nov 2, 2020 at 22:21
• Have you tested your code, e.g. on a simple exam like abc? Does it add the permutation cba to the set for that input? Nov 3, 2020 at 1:32
• Here is the original test, @M.Doerner, TestSolve.kt. I'm missing the permutation cba. I'll add that to the test and begin debugging to understand why cba is not covered in the algorithm. Nov 4, 2020 at 20:24

✅ Solution

🔧 Fix - Missing Combinations

1. Recursively generate each permutation of characters.
2. For every permutation, iterate through each index and move the last character to each position of the permutation.
3. Add each permutation to the Set.
fun getPerms(input: String): HashSet<String> {
val perms = hashSetOf<String>()
if (input.length <= 1)
return hashSetOf(input)
val allCharsExceptLast = input.substring(0, input.length - 1)
val permsOfAllCharsExceptLast = getPerms(allCharsExceptLast)
val lastChar = input.substring(input.length - 1)
for (s in permsOfAllCharsExceptLast) {
for (i in 0.. allCharsExceptLast.length) {
perms.add(s.substring(0, i) + lastChar + s.substring(i))
}
}
return perms
}


🔎 Questions

1: How does the problem change if the string can have duplicate characters?

Considering the input aaaaaaaaaaaaaaaaaaaaaa, it would return one combination. However, the algorithm would check each possible combination at every index which is highly inefficient. For example, with input aaa, the algorithm would run 9 times for the character at index 0, 1, and 2 for all 3 positions, so 3 x 3 iterations.

2: What is the space and time complexity?

Considering the input abcdefghijklmnopqrstuvwxyz, it seems like the space complexity grows larger than O(n^2) and closer to O(n^n), exponential growth.

3: How to optimize the time complexity?

If we take a simple example with one repeated character, a, in the input abac, the second combinations of a at index 2 are entirely repeated throughout the rest of the iterations.

Therefore, if a character value is a repeat value the iterations for the repeated value should be skipped. The algorithm may be adjusted to store an instance variable set of characters already searched for to improve the time efficiency.

Index 0

abac
baac
baac
baca

Index 1

baac
abac
aabc
aacb

Index 2: This is the second time using character a, therefore, we can skip these iterations.

aabc
aabc
abac
abca

Index 3

caba
acba
abca
abac

• It looks like my comments above (on your question) helped out? Nov 3, 2020 at 13:33
• Under 3, you show the entire output of your code for the input abac. Note that this does not contain the permutation caab. You might want to reconsider your original algorithm and actually test that it is a solution to the base question. Nov 3, 2020 at 22:38
• Thank you @SimonForsberg! Your comments on the space complexity and how to think about duplicates inspired the answer above. Now I need to debug my current solution as it is missing a permutation. Nov 4, 2020 at 20:16
• Great find @M.Doerner! Thank you. I'll update the existing test under src/test/TestSolve.kt to debug the algorithm. Nov 4, 2020 at 21:12