FCC Advanced Algorithm Scripting Challenge – No Repeats Please

There are a couple algorithms that are consistently asked about in the FCC forums because people are having trouble coming up with a solution. ‘No Repeats Please’ is definitely one of them…

No Repeats Please

In my opinion, the best place to start any of the algorithm scripting challenges is making sure you completely understand the problem.

Here is the challenge as stated by FCC:

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 (abaand aba) don’t have the same letter (in this case a) repeating.

Ok, not exactly the clearest of problems… In my opinion, there are two concepts in this algorithm that add to the difficulty.

First, we’re going to have to understand what permutations are and how to find all of them for a given string. Once we have that, we’ll need to write a regular expression (regex) that looks for repeated letters in each permutation.

Let’s get a better understanding of each of these concepts before we attempt to solve the algorithm challenge.

What are permutations?

The wikipedia page on permutations is a pretty good start if you haven’t been exposed to permutations previously. It states:

In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting. These differ from combinations, which are selections of some members of a set where order is disregarded.

The key takeaway from this should be that a permutation involves all the members of the set and the order matters.

Part of the given problem states that we should ‘assume that all characters in the provided string are unique’. This means that for the given example, ‘aab’, the first two letters should be considered unique even though they are both the letter ‘a’. Therefore, the two permutations without repeats, ‘aba’ and ‘aba’, are considered unique and we must count each of them in the solution.

A quick side note… If you’re looking for further clarification as to the difference between a permutation and a combination, this website does a good job comparing the two…

How can we find all permutations of a string?

Permutations are prevalent throughout many areas of mathematics and computer science. It should, therefore, be no surprise that there is a well known algorithm, called Heap’s Algorithm, that will find all the permutations for a set of objects.

Keep in mind, there are n! number of permutations for a set of n objects. So for a string of four letters there are (4 x 3 x 2 x 1) or 24 unique permutations.

Consequently, Heap’s algorithm works on the order of O(n!), the slowest order of functions. Therefore, as the set gets larger, increases of even one number will cause the algorithm to slow drastically. To put that into perspective, a set with 15 elements, will have over 1.3 Trillion permutations.

Ok, enough about the theory of permutations, how do we implement Heap’s algorithm?

Heap’s Algorithm

At this point, I’ll only post the pseudocode for Heap’s Algorithm found in Wikipedia, in case there is anyone reading this who is trying to solve ‘No Repeats Please’ and wants to attempt to implement in JavaScript on their own.

Given this isn’t a post specifically about Heap’s Algorithm, I’m not going to go into depth about how it works. Suffice to say that it systematically switches one pair of elements in each step, eventually yielding every possible permutation.

I encourage you to walk through the algorithm until you understand the workings ‘under the hood’. The image to the right shows the order of the elements after each iteration of Heap’s Algorithm for a set of 4 elements.

Here is the psuedocode for the recursive version of Heap’s algorithm. If you prefer to implement non-recursively, there is a version on the algorithm’s Wikipedia page.

procedure generate(n : integer, A : array of any):
    if n = 1 then
          output(A)
    else
        for i := 0; i < n - 1; i += 1 do
            generate(n - 1, A)
            if n is even then
                swap(A[i], A[n-1])
            else
                swap(A[0], A[n-1])
            end if
        end for
        generate(n - 1, A)
    end if

procedure generate(n : integer, A : array of any):

if n = 1 then

output(A)

else

for i := 0; i < n - 1; i += 1 do

generate(n - 1, A)

if n is even then

swap(A[i], A[n-1])

else

swap(A[0], A[n-1])

end if

end for

generate(n - 1, A)

end if

Let’s move on to regular expressions before we put everything together in the final algorithm.

Regular Expressions (RegExp)

In JavaScript, regular expressions are objects used to describe patterns of characters in text. They’re extremely useful when solving certain problems IF you know how to use them. That’s a big if, because they are very unintuitive to use and a weakness of many beginner programmers.

w3schools shows the syntax of regular expressions as /pattern/modifiers; . Rather than diving down the rabbit hole of regular expressions, I’ll point out some great resources to learn regex, then write and explain the one we’ll need to solve this challenge.

MDN is a good intro and explains most of what you’ll need for this challenge. For further learning, Eloquent JavaScript has an entire chapter on regular expressions. This site will let you practice writing them, and if you’re feeling really ambitious, although I haven’t read it, Mastering Regular Expressions was highly recommended by multiple people on the FCC forums.

A Regex for Repeating Letters

Let’s build a regex that will recognize repeating characters. We’ll start with /[a-zA-Z]/, which will match any and every letter in the string.

Patterns in parentheses are remembered and can be referenced in order (i.e. the pattern in the first set of () can later be referenced as \1 , the second as \2 and so on). Therefore, adding parenthesis like so, /([a-zA-Z])/, causes the letter that is matched to be remembered.

Next, adding \1 after ([a-zA-Z]) will cause the regex to look for a repeat of whatever the ([a-zA-Z]) matched (i.e. a pair of the same letter), which is what we need!

Therefore, our regex for finding a repeating letter is going to look like this /([a-zA-Z])\1/ .

Crystal clear right!!

An Additional Note on Regular Expressions

It’s important to note regular expressions are objects in JavaScript and inherit the methods associated with the RegExp prototype.

To solve ‘No Repeats Please’, we’ll be using the RegExp.test() method. When the test method is passed a string, it will return a Boolean telling you if that string contained the pattern. So /([a-zA-Z])\1/.test(str) will return true if there are repeating letters in str.

Structuring the Algorithm

Now that we have a better idea of the problem, we can start thinking about how to solve it… There are a couple ways we can structure this algorithm.

One, we could use Heap’s algorithm to iterate through all permutations of the given string, pushing each onto an array. Then, having an array with all permutations, we could check each element of the array for repeats.

Or two, we could use Heap’s algorithm to iterate through all permutations, each time checking for repeats and if not found, increment a counter.

I chose to write it the second way with efficiency in mind. Given the function is on the order of O(n!), we don’t want to iterate through all permutations to create the array, then iterate through again checking for repeats.

This won’t make much of a difference for strings of length 5 or 6, but it will make a huge difference on longer strings. In fact, to demonstrate this, I tested the function written both ways.

When running the function the first way (iterating twice), a string of 10 characters took 3523ms vs 2287ms for a function written the second way. When I increased the string to 11 characters it took the second function 26,802ms while the first function failed due to lack of memory.

Now that we have a structure in mind for the algorithm, let’s finally go ahead and write it!

My Solution to ‘No Repeats Please’

If you want to take a stab a writing the solution on your own, now’s the time… I’m going to post the solution that I came up with below. Again, there are multiple ways to solve this algorithm challenge, this is just the one that I came up with.

Spoilers_ahead

function permAlone(str) {
   
//create variable to store number of perms without a repeat
var noDupes = 0;

//split string into array
var strArray = str.split("");
  
// Call with an array of the original string
findPerm(strArray.length, strArray);
  
return noDupes;

//Heap's Algorithm
function findPerm(n, arr) {
    // If only 1 element, just output the array
    if (n == 1) {
//check for duplicates
     if(!(/([a-zA-Z])\1+/).test(arr.join(""))){
        noDupes += 1;
        }
      return;
    }

    for (var i = 0; i < n; i+= 1) {
        findPerm(n - 1, arr);

        // If n is even
        if (n % 2 === 0) {
            swap(i, n - 1);
        } else {
            swap(0, n - 1);
        }
    }

 function swap(idxA, idxB) {
    var tmp = arr[idxA];
    arr[idxA] = arr[idxB];
    arr[idxB] = tmp;
    }
  }
}

//call permAlone() with any string
permAlone("aab");

function permAlone(str) {

//create variable to store number of perms without a repeat

var noDupes = 0;

//split string into array

var strArray = str.split("");

// Call with an array of the original string

findPerm(strArray.length, strArray);

return noDupes;

//Heap's Algorithm

function findPerm(n, arr) {

// If only 1 element, just output the array

if (n == 1) {

//check for duplicates

if(!(/([a-zA-Z])\1+/).test(arr.join(""))){

noDupes += 1;

}

return;

}

for (var i = 0; i < n; i+= 1) {

findPerm(n - 1, arr);

// If n is even

if (n % 2 === 0) {

swap(i, n - 1);

} else {

swap(0, n - 1);

}

function swap(idxA, idxB) {

var tmp = arr[idxA];

arr[idxA] = arr[idxB];

arr[idxB] = tmp;

}

//call permAlone() with any string

permAlone("aab");

If you were having trouble with ‘No Repeats Please’, hopefully breaking it down like this helped. This is definitely one of the hardest of the FCC algorithm challenges.

I hope you found this post useful… If so, feel free to leave a comment and let me know. Thanks for reading, that’s all for now…

-Jeremy