JavaScript Algorithms: No Repeats Please

This freeCodeCamp challenge reads as follows:

Return the number of total permutations of the provided string that don’t have repeated consecutive letters. Assume that all characters in the provided string are each unique.

For example, aab should return 2 because it has 6 total permutations (aab, aab, aba, aba, baa, baa), but only 2 of them (aba and aba) don't have the same letter (in this case a) repeating.

A few questions come up when reading this challenge.

1. What is a permutation?
2. How do I get a list of all possible permutations?

What are permutations?

A permutation is one possible ordering of a set. When someone asks for the permutations of a set, normally they’re referring to all possible orderings of a set. So for example, if you’re asked to give the permutations of abc, the answer would be:

abc
acb
bac
bca
cab
cba

Fun fact: the total number of permutations of a set can be determined by getting the factorial (!n) of number of items in the set (I go over factorials in detail in this post). Permutations, like factorial, grow exponentially as the number of items in the set increase. A set with 10 items would have well over 3 million possible permutations!

Getting a list of permutations

The easiest way to approach this is to think about each item in the set in isolation from the rest of the items in the set. So when asked to get the permutations of abc, you think:

aPerms = a + total combination of rest of items in set
bPerms = b + total combination of rest of items in set
cPerms = c + total combination of rest of items in set
totalPermutations = aPerms + bPerms + cPerms

Spelled out, this would look like:

aPerm = "a" + "bc" || "cb"
bPerm = "b" + "ac" || "ca"
cPerm = "c" + "ab" || "ba"

By doing this you can see (in this case) it’s pretty simple. When you remove a from abc you’re left with bc and we know intuitively that bc has only two possible orderings (bc and cb). So all possible orders where the list starts with a is only:

abc
acb

Follow the same pattern with the other items in the set and you get all possible orderings:

abc
acb
bac
bca
cab
cba

An observation: we notice that each item can only occupy the first position in the list two times — that is the factorial of one less than the number of items in the set (!2). If the set was abcd we would expect a to occupy the first position exactly 6 times because !3 is 6. If the list was abcde, a would be in first position 24 times. If it was abcdef, that number would be 120!

What if the number of items is greater than 3?

Well, we learn above that we can break it down to a point where it’s possible to figure it out intuitively. What’s stopping us from continuing with this pattern for more complicated sets?

Say we have a set with four items: abcd. The same logic as before applies to the scenario as well:

aPerm = (("bc" || "cb") + "d") || ("dc" || "cd" + "b") || ("bd" || "db"+ "c")
aPerm = [abcd, acbd, adcb, acdb, abdc, adbc]

How do we do this in JavaScript?

If you attempt to do this in JavaScript without an algorithm, you’ll quickly get discouraged. You can do it (sort of) with 'abc':

const bc = ['bc', 'cb'];
const ac = ['ac', 'ca'];
const ab = ['ab', 'ba'];
const aPerms = [];
bc.forEach(rest => {
  aPerms.push('a' + rest);
});
const bPerms = [];
ac.forEach(rest => {
  aPerms.push('b' + rest);
});
const cPerms = [];
ab.forEach(rest => {
  aPerms.push('c' + rest);
});
const totalPerms = [...aPerms, ...bPerms, ...cPerms];
console.log(totalPerms) // `["abc", "acb", "bac", "bca", "cab", "cba"]`

Once the number of items in the set grows beyond 3, things really start to get out of hand:

const bcd = ['bcd', 'bdc', 'cbd', 'cdb', 'dbc', 'dcb'];
const acd = ['acd', 'adc', 'cad', 'cda', 'dac', 'dca' ];
const abd = ['abd', 'adb', 'bad', 'bda', 'dab', 'dba'];
const abc = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba'];
const aPerms = [];
bcd.forEach(rest => {
  aPerms.push('a' + rest);
});
const bPerms = [];
acd.forEach(rest => {
  aPerms.push('b' + rest);
});
const cPerms = [];
abd.forEach(rest => {
  aPerms.push('c' + rest);
});
const dPerms = [];
abc.forEach(rest => {
  aPerms.push('d' + rest);
});
const totalPerms = [...aPerms, ...bPerms, ...cPerms, ...dPerms]; 
console.log(totalPerms) // returns `["abcd", "abdc", "acbd", "acdb", "adbc", "adcb", "bacd", "badc", "bcad", "bcda", "bdac", "bdca", "cabd", "cadb", "cbad", "cbda", "cdab", "cdba", "dabc", "dacb", "dbac", "dbca", "dcab", "dcba"]`

How do we do this using a function?

Enter recursion…

Recursion, simply put, is when a function calls itself (I talk about recursion in great detail in my post about factorial). This post also explains recursion really well but to boil it down, I’ll just borrow the example from it:

function countDown(n) {
  console.log(n);
  if (n >= 1) countDown(n-1);
}
countDown(10);

So what’s happening here? Let’s walk through it. countDown(10) is called and it immediately encounters console.log(n) so it logs out 10. Then it hits the conditional statement asking whether n is greater than 1. It is! So we continue and call countDown() again, but this time we subtract 1 from 10 to get 9. Rinse and repeat until we get to 0. And that’s how recursion works. Pretty simple, right?

So how can we use this to achieve our objective. Before I can answer that I need to get something off my chest: I was not able to figure out how to write a permutations function in JavaScript on my own. Gasp! Yeah, I know. It’s embarrassing to have to admit to it but try as I may, it was just too complicated for me to figure out (being that math is not exactly my strong suit). However when I discovered a solution, I was well equipped to understand what was going on because I happened to know a thing or two about recursion. Here’s what I found:

What’s going on here? Well, when getAllPermutations is called it first checks to see if string is only 1 character long. If that’s the case, no need to do additional work. Just put it in an array and return it. If it’s longer than one character we enter a for loop and get the first character from the string and assign it to a variable called firstChar. We then get the remaining characters and assign them to another variable called charsLeft.

This is where things get a little weird. Using the charsLeft, we call getAllPermutations again (recursion). That call continues to call itself until it gets to a single character which gets caught by if (string.length === 1). This gets returned and added to whichever nested recursion function it happens to be in all the way up the line until you get to the original for loop where it is finally added to the original firstChar once for each permutation in innerPermutations. Finally the loop continues on to the next character where it starts the process all over again. Whew! That’s a lot of recursion.

Putting it all together

Here’s what needs to happen to solve the original problem:

The original problem is asking for total permutations but with a slight twist. Instead of returning all permutations, it wants you to throw out any permutation that have two of the same characters side-by-side. So basically we’re just going to run the same permutations function we talked about earlier and then run the results through another loop that will filter out any permutations with repeating characters. Here’s a basic outline:

1. Validate the input (must be a string and cannot be an empty string).
2. Get all the permutations (the specifics of how we did this are discussed above and code was modified using example found here).
3. Define a method (hasRepeat) that simply returns true or false if a string contains repeated characters.
4. Loop through all the permutations and call hasRepeat with each. If it returns false, add it to a new array.
5. Finally, count the new array and return the count.

Solution