Here’s the description of the problem:
“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.”
The hints are:
Permutations – this is basically finding all the ways that a combination of items can be rearranged. So, for example, if you have three letters (as in this exercise) you can rearrange them six ways – abc: abc acb bac bca cab cba. There’a whole lot of theory here; go ahead and explore the link if you’d like.
RegExp – Regular Expression. We’ve touched on these before, and I noted then that this was good for about a dozen posts. So I suggest that you check out the page on MDN.
Here’s the code they give you to start with:
Yes, well, that’s very helpful guys. Thanks for that. Very not helpful.
I had really no idea how to start. I mean, I could see that I needed to loop through the string, I could use substr() to give me parts of the string that I could recombine to get the different permutations, and that it would involve some sort of recursion to go through the substrings, but beyond that, I was a little baffled. So, step 1, Google it!
It turns out there are a TON of permutation algorithms out there. But I didn’t want to just copy one – as I’ve noted in almost every previous blog post on a challenge, you don’t learn anything if you just copy and paste. So I started deconstructing them, taking them apart, trying to figure out how they worked and what each part did. Some of them, I found, were way too complicated and could be done an easier way. Others were obviously written by someone with a lot of experience; they used all kinds of shortcuts. Each one had a different concept of what should be included in what scope. So when you look at my code below, remember that this is just the way I did it, and that there are many other ways.
var string = str;
Perms is an array that’s going to hold all the permutations; string holds the string value that you want permuted.
So, when you first pass the values to the function, the first letter hasn’t been set yet, so we set it to 0. You’ll see why we did this below.
When we hit the end of the string, push the value to an array that’s going to hold all the permutations.
This is the heart of the function. We’re looping through the string, and recombining the letters in a string named ‘s1’. Then we call permute() again from WITHIN permute() until we have hit the end of the string. This is called recursion and, to my mind, is one of the hardest concepts in programming to master. But it’s very powerful and if you can get it, it will open up a whole new world to you. The easiest way to figure out what is going on here is to write it out by hand at each step, watching how the values change.
Finally, we call the function on a string:
But, this isn’t quite right yet. The idea here is to delete all the permutations that have the same letter in a row, and return the amount of entries left, whereas the code above merely returns the number of permutations the string has. Theoretically, we didn’t even need to write this code to figure out the number of permutations; we could have just taken the number of items – 3, and found its factorial – 3!, which is 3 x 2 x 1 or 6, and returned that number. Instead, we generated all the permutations so that we could determine which ones had duplicate letters. So let’s look at how to do that now.
So, my first attempt to get rid of the ones that had two of the same letters went like this:
Update: Got it! The filter() function should be familiar from my post here and the Inventory Update challenge. The Regex threw me for awhile though. I kept trying /w, from the MDN page, and not getting an answer. Then I figured out that it was literally looking for a ‘w’. The period was the right symbol to use to match any character. I also had no parentheses around my period, which is for capture. This ‘remembers’ the character, so it can match it to the previous character in the string. Finally, I tried it as an if statement and that got messy. So I just condensed the statement to return the items that needed to be in the array (answer). I forgot the not symbol at first ( the !) and I kept getting it wrong until I figured out that I was getting the opposite of what I wanted, and that made me realize I was returning the wrong set of strings. So, here’s the final solution:
Okay, on to the next challenge, which is Friendly Date Ranges!