Lesson

Write a function to print all distinct permutations of a string that contains duplicates. Given an input string, write a function to print all possible unique permutations of the string without any duplicates.

Sample Input:

`const input = 'ABCA';`

Sample Output:

```
ABCA
ABAC
ACBA
ACAB
AABC
AACB
BAAC
BACA
BCAA
CAAB
CABA
CBAA
```

First, let's take a look at the problem we're trying to solve. We want to print all distinct permutations of a string that contains duplicates. To solve this problem, we are going to use a recursive algorithm that generates permutations by swapping characters in the input string.

```
function findPermutations(string) {
// Edge case, return the string if it contains only one character or is empty
if (string.length <= 1) {
return [string];
}
// Initialize empty array to store permutations
const permutations = [];
// Loop through each character in the string
for (let i = 0; i < string.length; i++) {
const character = string[i];
// Check for duplicates, continue the loop if the character has already been used
if (string.indexOf(character) !== i) {
continue;
}
// Generate remaining string by slicing the original string from i + 1 to the end
const remainingString = string.slice(0, i) + string.slice(i + 1);
// Generate permutations of the remaining string using recursion
for (let subPermutation of findPermutations(remainingString)) {
// Add the character and sub-permutation to the permutations array
permutations.push(character + subPermutation);
}
}
return permutations;
}
```

`findPermutations`

We check if the length of the input string is less than 2. If it is, we return the string itself because there is only one permutation possible in this case.

- If the length of the input string is 2 or greater, we create an empty array called
to store the permutations.`permutations`

We loop through each character in the input string. For each character, we check if it has already been used for a permutation by looking at its index in the string. If it has been used, we skip the swapping step and continue with the next character.

- If the character has not been used yet for a permutation, we create a new string called
that contains all the characters after the current character.`remainingString`

- We call the
function recursively on the`findPermutations`

to generate all the permutations of the remaining characters.`remainingString`

- For each permutation generated by the recursive call, we add the current character to the beginning of the permutation and push it into the
array, but only if it is not a duplicate.`permutations`

- After the loop is finished, we return the
array.`permutations`

`permutations`

Although the time complexity is high, it is an inherent property of the problem, as the number of permutations possible for a given string is n!, and we need to check all of them to ensure that there are no duplicates. We can optimize the solution by pruning the recursion tree when we encounter duplicates, but that would not significantly affect the time complexity.