Distinct Permutations Of A String


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:



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) {

    // 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
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
    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
    that contains all the characters after the current character.
  • We call the
    function recursively on the
    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
    array, but only if it is not a duplicate.
  • After the loop is finished, we return the
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

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.