Program to print all the permutation of string

Learn how to implement an algorithm to print all the permutation of a string in javascript.

Example

Input:
"AB"
"ABC"

Output:
"AB"
"BA"

"ABC"
"ACB"
"BAC"
"BCA"
"CBA"
"CAB"

Implementation

• We are going to use the backtracking technique to print all the permutation of a string.
• We will create a function which will print the permutation of the string if the first index and last index of string is equal.
• If they are not equal then we will swap the characters of the string for each index and call the permute function recursively.
• This way it will generate all the possible permutation and print them.
• To swap the characters we will use another function.

This is how backtracking technique works for the string ‘ABC’.

let permute = (str, left = 0, right = str.length - 1) => {
  //If left index is equal to right index
  //Print the string permutation
  if(left == right){
    console.log(str);
  }else{
    for(let i = left; i <= right; i++){
      //Swap the letters of the string
      str = swap(str, left, i);
      //Generate the permutation with swapped letters
      permute(str, left+1, right);
      //Restore the letters back to their position
      str = swap(str, left, i);
    }
  }
}

//Function to swap the letters of the string
let swap = (str, left, right) => {
  let arr = str.split('');
  [arr[left], arr[right]] = [arr[right], arr[left]];
  return arr.join('');
}

Input:
permute('AB');
permute('ABC');

Output:
"AB"
"BA"

"ABC"
"ACB"
"BAC"
"BCA"
"CBA"
"CAB"

Time complexity: O(n * n!).
Space complexity: O(n!).

Time and Space complexity

• For any given string of length n there are n! possible permutations, and we need to print all of them so Time complexity is O(n * n!).
• The function will be called recursively and will be stored in call stack for all n! permutations, so Space complexity is O(n!).