# 8.7 Permutations Without Dups

### yuliakononchuk ・2 min read

CrackingTheCodingInterview (6 Part Series)

######
**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

CrackingTheCodingInterview (6 Part Series)