Coding Interview Question: String Permutations.

Please follow & like us :)

Many Big Tech Companies like Google, Facebook, Amazon ask coding question about string permutations.

In this post, we are covering the logical solution of string permutation and also implementation using JavaScript.

Question: Write a program to print all permutations of a given string.

Here are the example:

If you have given Input: “ab”, then expected output would be: [ab, ba]

If you have given Input: “abc”, then expected output would be: [abc, acb, bac, bca, cab, cba]

If you have given Input: “abcd”, then expected output would be: [abcd, abdc, acbd, acdb, adbc, adcb, bacd, badc, bcad, bcda, bdac, bdca, cabd, cadb, cbad, cbda, cdab, cdba, dabc, dacb, dbac, dbca, dcbd, dcdb,]

In general, possible permutations are => n! where n is string length.

That means if we take a look at sample inputs, then for Input1 = 2! = 2×1 = 2 for Input2 = 3! = 3x2x1 = 6 for Input3 = 4! = 4x3x2x1 = 24

In this examples, basically we are keeping one character fixed and finding possible permutations for remaining characters.

Graphical Overview of String Permutations.

String Permutation

Here is pseudo code:

let str = 'abc';
const getPermutations = (str) => {
  let results = [];
  // first we have to scan the string
  
  for (let i = 0; i < inputstring.length; i++) {
    
    // then we will keep one char fixed
    // for input string "abc" at i = 0 a will b fixed, at i=1 b will be fixed, at i=2 c will be fixed.
    
    let fixedChar = inputstring[i]; // example: a
    
    // for remaining characters we will recursively find all possible permutations 
    
    let permRemang = getPermutations(remainingchars); 
    // example: [bc, cb]
    // Now we will add first char to bc, cb value.
    
     for (let j = 0; j <  permRemang.length; j++) {
       results.push(fixedChar + permRemang[j])
     }
  }
  return results;
}

Now we understood logic and pseudo code, we can start writing recursive algorithm which will print all possible permutations for given string.

const getAllPermutations = (string) => {
    let results = [];

    if (string.length === 1) {
        results.push(string);
        return results;
    }

    for (let i = 0; i < string.length; i++) {
        let firstChar = string[i];
        let charsLeft = string.substring(0, i) + string.substring(i + 1);
        let innerPermutations = getAllPermutations(charsLeft);
        for (let j = 0; j < innerPermutations.length; j++) {
            results.push(firstChar + innerPermutations[j]);
        }
    }
    return results;
}
console.log(getAllPermutations('abc'));