Distinct Permutations Of A String

Mark as Completed

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

Walkthrough

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;
}

Here is how the findPermutations
function works:

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 permutations
to store the 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 remainingString
that contains all the characters after the current character.
We call the findPermutations
function recursively on the remainingString
to generate all the permutations of the remaining characters.
For each permutation generated by the recursive call, we add the current character to the beginning of the permutation and push it into the permutations
array, but only if it is not a duplicate.
After the loop is finished, we return the permutations
array.

Big O Complexity Analysis: The time complexity of this solution is O(n! * n^2), where n is the length of the input string. This is because we have to generate all n! permutations, and for each permutation, we have to check if it is a duplicate, which takes O(n) time. The space complexity of this solution is also O(n!), as we have to store all the permutations in the permutations
array.

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.

Previous Lesson Next Lesson