Video Possible Solution
(This includes an explanation of the approach to thinking about the permutations. I suggest interviewers especially watch at least the first few minutes)
Additional Solution from Edwin
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' ]It's helpful to consider the desired behavior of the function on a character by character basis.
Start simple - a string of one character has only one permutation. In this case, the function should return a results array containing just that permutation.
For each subsequent character after the first one, that character needs to be added to each possible position (before, after, in between, etc) of each existing permutation already in the results array. This will be iterated for each of the remaining characters in the input string.
After all permutations have been generated, the results array should be deduped and sorted to satisfy the solution.
Input: 'one'
Iterate for character: 'o'
Result: ['o']
Iterate for character: 'n'
Result: ['no', 'on']
Iterate for character: 'e'
Result: ['eno', 'neo', 'noe', 'eon', 'oen', 'one']
Dedupe and sort:
Output: ['eno', 'eon', 'neo', 'noe', 'oen', 'one']
Input: 'app'
Iterate for character: 'a'
Result: ['a']
Iterate for character: 'p'
Result: ['pa', 'ap']
Iterate for character: 'p'
Result: ['ppa', 'ppa', 'pap', 'pap', 'app', 'app']
Dedupe:
Result: ['ppa', 'pap', 'app']
Sort:
Result: ['app', 'pap', 'ppa']
To help encourage your interviewee, I have a suggestions on some pointed questioning that may help. These are very general in nature, not specific to this REACTO, and completely optional!
- What is the unknown you're solving for?
- What is the data that is provided to you?
- What is the condition for success?
- Is it possible to satisfy the condition? How about satisfying a part of the condition?
- Can you restate the problem?
- What does this problem look like? Do you know of a related problem?
- Can you use the related problem? Can you introduce a new element in order to make it useable?
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:
const stringPermutations = str => {
let results = [];
let letters = str.split('');
results.push([letters.shift()]); //add first letter (as an array) to results
while (letters.length) {
let curLetter = letters.shift();
let tmpResults = [];
results.forEach(wordArr => {
for (let i = 0; i <= wordArr.length; i++) {
var tmp = wordArr.slice(); //make copy so we can modify it
tmp.splice(i, 0, curLetter); //insert the letter at the current position
tmpResults.push(tmp); //reassign
}
});
results = tmpResults; //overwrite the previous results
}
return results
.map(letterArr => letterArr.join(''))
.filter((el, index, self) => self.indexOf(el) === index) //filter out non-unique words,
.sort();
}...a similar solution, but recursive might look like:
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();
}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);
}