8.7 Permutations Without Dups

NB: This post is a part of the series of solving the challenges from 'Cracking The Coding Interview' book with JavaScript. I'll post only the challenges I've figured out on my own - and will try to describe my reasoning behind the solution. Any ideas on how to solve it differently or in a more optimal way are very welcome 😊

Write a method to compute all permutations of a string of unique characters.

I've approached this one by taking a specific example: finding all permutations of 123. Permutations are all the possible combinations of elements, so from 123 we need to get the following ones: 123, 132, 213, 231, 312, 321 - 6 in total. Let's say we knew all permutations of a string of 12, could we then somehow get the permutations of 123? Sure! See the drawing:

We know that permutations of 12 are 12 and 21 - and it looks like we just need to add 3 to every possible position for each of those arrays in order to get out result 🎉(result should be all arrays in the pink circle). The transition from 1 to 12 works in a similar way: to get all permutations of 12 we just need to put 2 in all possible indices in the string of 1 - either before 1 (21) or after (12).

In Javascript this logic can be reflected by the following code:

function getPermutations(str) {
  const lastIndex = str.length - 1;
  const lastChar = str[lastIndex];
  if (lastIndex === 0) { return [str]; }
  const prev = getPermutations(str.slice(0, lastIndex));
  return prev.flatMap(elem => {
    const result = [];
    for (let i = 0; i <= lastIndex; i ++) {
      const newElem = elem.slice(0, i) + lastChar + elem.slice(i);
      result.push(newElem);
    }
    return result;            
  });
}

With getPermutations(str.slice(0, lastIndex)) we're calculating the permutations of a shorter string (string without the last character), and then mapping over the array of these permutations. Each element in the map is then looped over, so that we could create a set of new strings with added last character. This way, for an element 12, we would be able to return [312, 132, 123]. Finally, flatMap allows to return the result as one array - [312, 132, 123, 321, 232, 213] instead of [[312, 132, 123], [321, 232, 213]] - which is convenient for the next iteration of the recursion