Generate unique string permutations recursively

Question

🧩 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)
            set.add(combo.substring(0, i) + input.get(lookAtIndex) +
                    combo.substring(i))
        }
        allPerm(input, lookAtIndex + 1, set)
    }
    return set
}

See: GitHub

Answer 1

✅ 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