Given a string, return an array of all the permutations of that string. The permutations of the string should be the same length as the original string (i.e. use each letter in the string exactly once) but do not need to be actual words.
The array that is returned should only contain unique values and its elements should be in alphabetical order.
stringPermutations('one');
// should return [ 'eno', 'eon' 'neo', 'noe', 'oen', 'one']
stringPermutations('app');
// should return [ 'app','pap','ppa']
stringPermutations('nn'); //should return [ 'nn' ]Whenever you see the words "permutations" or "subsets", you should think of n factorial or n! You will potentially(not always) have to check for all the possible combinations of n - depending on what the question is asking for. In this case, we're looking for every permutation of the str where str.length === permutation.length. At worst case, n === str.length! (see example 1).
You will need to write a function to generate the str's permutations. There are many ways to do this so feel free to let the interviewer take any path that makes sense to them. Once you get all the permutations that satisfy the condition (str.length), you just have to push it into your result array.
In general we're pretty stuck with O(n!) (factorial) time and space complexity (where n is the number of unique characters in the string). Frankly, the end result of the algorithm demands it, because for n possible characters, it turns out there are n! permutations of those characters.
For generating all possible permutations we could imagine doing so "position by position". There are n possible characters for the first position in the string. Each of those possibilities has n-1 possibilities for the second position (i.e. excluding the character we put in the first position). In turn each of those possibilities has n-2 possibilities for the third position (i.e. excluding the two characters already used for the first two positions). This continues until we reach the last character, which actually just has 1 possibility, because we will have used all other characters at that point. So n possibilities times n-1 possibilities times n-2 possibilities until we reach 1—that is exactly what n! is! You may find an explanation that is figuratively and literally more drawn out here.
So one important lesson to take from this exercise: permutations problems will tend to be factorial time and space complexity.
The following solution iteratively generates all possible permutations then sorts that result:
function stringPermutations(str) {
var results = [];
var letters = str.split('');
results.push([letters.shift()]); //add first letter (as an array) to results
while (letters.length) {
var curLetter = letters.shift();
var tmpResults = [];
results.forEach(function(curResult) {
for (var i = 0; i <= curResult.length; i++) {
var tmp = curResult.slice(); //make copy so we can modify it
//insert the letter at the current position
tmp.splice(i, 0, curLetter);
tmpResults.push(tmp);
}
});
results = tmpResults; //overwrite the previous results
}
return results
.map(function(letterArr) {
return letterArr.join('');
})
.filter(function(el, index, self) {
return self.indexOf(el) === index; //filter out non-unique words
})
.sort();
}Time Complexity - O(n!), Space Complexity - O(n!)
There is a similar approach using recursion which is also known as backtracking. "Backtracking is a general algorithm approach for finding all solutions to certain computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate as soon as it determines that the candidate cannot possibly be completed to a valid solution." Thanks Wikipedia.
In other words.. you want to start with the whole str and backtrack, beginning from the first letter. Backtracking will follow every possible path (can also be seen as a partial solution) until it reaches your base case(the permutation) that you've set up OR it no longer satisfies the condition that the problem asks for.
- Initialize a results arr and a recursive function, getPerms that will take in a str and an array as arguments.
- getPerms will have a base case where the str is completely empty because the arr will contain all permutations of the letters. When you hit this case, you've found a permutation.
- Loop through the array of letters. You want to take out the first letter and push it into your array that's keeping track of the possible permutations.
- You want to recursively call getPerms so that the new call will have the str without its first letter but the array will store that letter.
- Each recursive call will take its possible combinations minus the initial letter and if it satisfies the base case, you've used all the letters and you push the permutation into the results arr as a string.
- after you've checked and went through all of its recursive calls from the FIRST letter, you have to remember to remove that letter from the array but also replace the letter back in its original string so that you dont forget to check it in its following iterations.
- Sort && Filter the results array and return it.
function recursiveStringPermutations(str) {
var results = [];
getPerms(str, []);
function getPerms(str, arr) {
if (typeof str === 'string')
//on first call, split the string into an array
str = str.split('');
if (!str.length)
//base case- push the compiled results into the results variable
results.push(arr.join(''));
for (var i = 0; i < str.length; i++) {
var letter = str.splice(i, 1);
arr.push(letter);
getPerms(str, arr); //recursive call
arr.pop();
str.splice(i, 0, letter);
}
}
return results
.filter(function(el, index) {
return results.indexOf(el) === index; //filter out non-unique words
})
.sort();
}Time Complexity - O(n!), Space Complexity - O(n!)
Here is a solution that implicitly keeps the results sorted as it generates them (an optimization):
Without sorting before we start finding permutations, we will get n! _ log(n!) -- we have an array that is n! in length at that point. If we sort before our sort time is n _ log(n). In both situations, n is the length of the input string. Overall, finding all string permutations is n!
// finds all possible permutations *while* maintaining the order of the characters
function stringPermutations(str) {
if (str.length === 1) return [str]; // base case
const all = [];
// go through each character in the string
let i = 0;
while (i < str.length) {
// get each individual character
const letter = str[i];
// get all the other characters surrounding it
const otherChars = str.slice(0, i) + str.slice(i + 1);
// compute all permutations of the *other* characters
stringPermutations(otherChars).forEach(submpermut => {
// add the current letter to the front of each of these "sub-permutations"
// include *that* into the full result set
all.push(letter + submpermut);
});
// increment until we reach a new letter (to avoid duplicates in the result set)
while (str[i] === letter) i++;
}
return all;
}
function sortedStringPermutations(str) {
// first sort the characters in the string
const sortedStr = str
.split('')
.sort()
.join('');
// then find the ordered permutations of that sorted string
return stringPermutations(sortedStr);
}