Generate unique string permutations recursively
✅ Solution
 Fix - Missing Combinations

Recursively generate each permutation of characters.
For every permutation, iterate through each index and move the last character to each position of the permutation.
Add each permutation to the Set.

fun getPerms(input: String): HashSet&lt;String&gt; {
    val perms = hashSetOf&lt;String&gt;()
    if (input.length &lt;= 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