StringPermutations.md

STRING PERMUTATIONS

THE QUESTION:

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.

Notes:

• The array that is returned should only contain unique values
• The array that is returned should be sorted alphabetically

Example:

makePerms('cat') => [ 'act', 'atc', 'cat', 'cta', 'tac', 'tca' ]

THE APPROACH:

1. Select each letter in the string one at a time.
2. Permute all the letters in the string except the selected one. This gives us an array of sub-permutations.
3. Concatenate the selected letter with each of the sub-permutations.

SOLUTION:

function makePerms (str) {

	if (!str.length) return [''];

	const perms = [];
	
	for (let i = 0; i < str.length; i++) {
		const currentLetter = str[i]; 
		const otherLetters = str.slice(0, i) + str.slice(i + 1);
		const subPerms = makePerms(otherLetters); 
		subPerms.forEach( subPerm => perms.push(currentLetter + subPerm) )
	}
	
	return perms
	.filter( (perm, index) => perms.indexOf(perm) === index )
	.sort();
}

View the solution on repl.it!

VISUALIZATION:

TIME COMPLEXITY:

In order to to analyze the time complexity of our algorithm, we must first determine what our input size is, i.e. what n stands for. In the case of this function, n is the length of our string.

There are two things to notice about this function that will allow us figure out its time complexity.

1. Within our function we have a for-loop of n-iterations, so each line of code within our for-loop will be run n-times.
2. Inside this for-loop we are recursively calling our function makePerms again with an input size of n - 1.

How how can we use these observations to figure out the time complexity of our function? To answer that, you must think carefully about what happens when we make that recursive call. Inside the recursive call, we have a for-loop of n-1 iterations, and inside of that we recursively call our function makePerms again with an input size of n - 2, which triggers another for-loop of n - 2 iterations, and inside of that we recursively call our function makePerms with an input size of n - 3... You can see where this is going! We keep recursively calling our function with an input size of one less than the previous input size, and this triggers a for-loop with that many iterations. We finally stop the recursion when the input size is equal to zero - that is our base case.

Let's diagram out what this looks like with an input value of 5:

O(n = 5) 
	* O(n-1 = 4) 
		* O(n-2 = 3)
			* O (n-3 = 2) 
				* O(n-4 = 1) 
				
				= 5 * 4 * 3 * 2 * 1

So the time complexity of our function is n factorial - 0(n!)

This makes sense because permutations are inherently factorial. There are 2! permutations of a two-letter word, 3! permutations of a three-letter word, 4! permutations of a four-letter word, etc... This means that it is impossible to write a string permutation algorithm that has a time complexity better than O(n!).