freeCodeCamp Algorithm Challenge Guide: No Repeats Please

freeCodeCamp Algorithm Challenge Guide: No Repeats Please
0

#1

:triangular_flag_on_post: Remember to use Read-Search-Ask if you get stuck. Try to pair program :busts_in_silhouette: and write your own code :pencil:

:checkered_flag: Problem Explanation:

This task requires us to return the number of total permutations of the provided string that don’t have repeated consecutive letters. It is to be assumed 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.

To achieve that, we’ll have to look at each possible permutation of a string. There are several ways to do that. A common interview question is building a function that collects all permutations of a string. There are several tutorials available on the internet on how to do that.

Potential Methods Used As Solution

Recursive Method

This task can be daunting even after watching a tutorial. To write a recursive solution, you will want to send each new use of the function three inputs:

  1. A new string (or character array) that is being built.
  2. A position in your new string that’s going to be filled next.
  3. An idea of what characters (more specifically positions) from the original string have yet to be used.

The pseudo code will look something like this:

var str = ???;
permAlone(current position in original string, characters used already in original string, created string) {
  if (current string is finished) {
    print current string;
  } else {
    for (var i = 0; i < str.length; i++) {
      if (str[i] has not been used) {
        put str[i] into the current position of new string;
        mark str[i] as used;
        permAlone(current position in original string, characters used already in original string, created string);
        remove str[i] as used because another branch in the tree for i + 1 will likely use it;
      }
    }
  }
}
permAlone(0, nothing used yet, empty new string (or array the same size as str));

Another way to think about this problem is to start from an empty space. Introduce the first letter to the space. This space will now contain the first sub-permutation. Here’s a diagram illustrating the idea:

Non-Recursive Method
// An approach to introduce a new character to a permutation
var ch = '?';
var source = ['?', '?', '?'];     // Current sub-permutation
var temp, dest = [];

for (var i = 0; i <= source.length; ++i) {
  temp = source.slice(0);         // Copy the array
  temp.splice(i, 0, ch);          // Insert the new character
  dest.push(temp);                // Store the new sub-permutation
}

Finding each permutation could then be done non-recursively by including the above in a function taking a source array and returning a destination array. For each letter of the input string, pass that character, as well as the array returned from the previous call of the function.

A way to visualize this is by considering a tree that starts with the first character of your string:

Relevant Links

:speech_balloon: Hint: 1

  • The easiest way is to use Heap’s algorithm to recursively get a list of all the permutations.

try to solve the problem now

:speech_balloon: Hint: 2

  • Once you have the list then just create a regular expression to catch the repeating characters.

try to solve the problem now

:speech_balloon: Hint: 3

  • You will want to have the permutations as an array of joined strings instead of separated characters.

try to solve the problem now

Spoiler Alert!

687474703a2f2f7777772e796f75726472756d2e636f6d2f796f75726472756d2f696d616765732f323030372f31302f31302f7265645f7761726e696e675f7369676e5f322e676966.gif

Solution ahead!

:beginner: Basic Code Solution:

function permAlone(str) {

  // Create a regex to match repeated consecutive characters.
  var regex = /(.)\1+/g;

  // Split the string into an array of characters.
  var arr = str.split('');
  var permutations = [];
  var tmp;

  // Return 0 if str contains same character.
  if (str.match(regex) !== null && str.match(regex)[0] === str) return 0;

  // Function to swap variables' content.
  function swap(index1, index2) {
    tmp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = tmp;
  }

  // Generate arrays of permutations using the algorithm.
  function generate(int) {
    if (int === 1) {
      // Make sure to join the characters as we create  the permutation arrays
      permutations.push(arr.join(''));
    } else {
      for (var i = 0; i != int; ++i) {
        generate(int - 1);
        swap(int % 2 ? 0 : i, int - 1);
      }
    }
  }

  generate(arr.length);

  // Filter the array of repeated permutations.
  var filtered = permutations.filter(function(string) {
    return !string.match(regex);
  });

  // Return how many have no repetitions.
  return filtered.length;
}

// Test here.
permAlone('aab');

:rocket: Run Code

Code Explanation:

  • regex contains the regular expression to match repeated consecutive characters.
  • The string str is split into an array of characters, arr.
  • 0 is returned if str contains same characters.
  • The function swap() is used for the purpose of swapping the contents of two variable’s contents.
  • The next block of code uses Heap’s algorithm to generate arrays of permutations in permutations.
  • The filtered variable filters permutations to include only non-repeated permutations.
  • filtered.length returns the number of total permutations of the provided string that don’t have repeated consecutive letters.

Relevant Links

:rotating_light: Advanced Code Solution:

function permAlone(str) {
  if(str=='') return 1
  const bag=new Map()
  for(const c of str){
    bag.set(c,(bag.get(c)||0)+1)
  }
  const essence=[]
  for(let v of bag.values()){
    essence[--v]=(essence[v]||0)+1
  }
  let fact
  {const f=[1]
    fact= n=>f[n]||(f[n]=n*fact(n-1))
  }
  const essL=essence.length
  let bits=essL//essence.reduce((s,v)=>s+v,essL)
  let bExp=-1// essence as a bits expression
  let pFact=1, bMask=1
  for(let i=0;i<essL && bits<=32;i++){
    if(essence[i]==null) essence[i]=0
    const v=essence[i]; bits+=v
    pFact*= fact(i+1)**v * fact(v)
    bExp-=bMask; bMask<<=v+1
  }
  if(bits>32) 
    throw `Too many bits requiered: ${bits} >32`
  bExp+=bMask--
  // console.log(essence)
  // console.log(bExp.toString(2))

  class MapA extends Map{
    set(key, idx, value){
      if(value==null)
        return super.set(key, idx),this
      let ar=super.get(key)
      if(typeof ar!='object')
        {ar=[]; super.set(key, ar)}
      ar[idx]=value
      return this
    }
  }
  let crMap=new MapA()
  crMap.set((3<<bits-essL-1)-1, 0, 1)
  for(let lcrM=1;lcrM<str.length; lcrM++){
    const nxMap=new MapA()
    for(const [key, value] of crMap){
      const bDiff=key^bExp, 
        bnSprout=~((~key&bMask)>>>1 & key),
        bnImp=~bDiff&bnSprout,
        sum=value.reduce((s,v)=>s+v,0)
      let i=0, v=0, allowed=0
      for(let crBit=1;crBit&bMask;crBit<<=1){
        if(crBit&key) v++; else {i++; v=0}
        if(crBit&bnImp) continue
        cLabel:{
          if(crBit&bDiff)
            if(crBit&key)allowed++
            else allowed--
          else break cLabel
          if(crBit&bnSprout) continue
        }if(allowed)
          nxMap.set(key+crBit, i, i?v*sum-value[i-1]:sum)
      }
    }
    //could be done: recycle crMap
    crMap=nxMap;
  }
  return pFact*crMap.get(bExp).reduce((s,v)=>s+v,0)
}

:rocket: Run Code

Code Explanation:

The problem asks to Return the number of total permutations not to generate them…Please follow my Gist for talk and explanations.

Relevant Links

:clipboard: NOTES FOR CONTRIBUTIONS:

  • :warning: DO NOT add solutions that are similar to any existing solutions. If you think it is similar but better, then try to merge (or replace) the existing similar solution.
  • Add an explanation of your solution.
  • Categorize the solution in one of the following categories — Basic, Intermediate and Advanced. :traffic_light:
  • Please add your username only if you have added any relevant main contents. (:warning: DO NOT remove any existing usernames)

See :point_right: Wiki Challenge Solution Template for reference.


Finally Beat "No Repeats Please"!
Stuck on "No repeats please"
#2

#3

#4

A lot of people have working Heap’s algorithm implementations,
although producing correct result, it is doing extra swaps.
Both the freeCodeCamp example here and geekForGeek example have this problem.
Even on Wikipedia, people are trying to argue that the pseudo code there with less but correct number of swaps is wrong although it is actually correct.

The correctness of Heap’s algorithm relies heavily on swapping the element correctly so that every elements is guaranteed to show up in the last position in each iteration.

With extra swaps, maybe one can still use mathematical induction to prove the algorithm still work correctly??
Otherwise, it is better to stick with the original proven version of Heap’s algorithm.
Besides that, non-necessary extra swaps cost more and not efficient.

For an array of N, there should be only (N! - 1) swaps
My implementation below is trying to maintain the (N! - 1) swaps logic.

// javascript is call by value by default,
// but when passing object it is passing the actual reference
function swap(index1, index2, arr) {
  var tmp;
  
  tmp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = tmp;
}

// check if characters repeat in string 
function checkRepeats (str) {
  var exp = /(\w)\1+/g;
  return exp.test(str);
}

/* Heap's algorithm with filtering out repeats
Heap's algorithm: https://en.wikipedia.org/wiki/Heap%27s_algorithm
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
*/
function generateNoRepeats(n, arr, result) {  
  if (n == 1) {
    // output(A) 
    if (!checkRepeats(arr.join(""))) {
      result.push(arr.join(""));
    }
  } else {
    for (var i = 0; i < n - 1; i++) {
      generateNoRepeats(n - 1, arr, result);
      if (n%2 === 0) {
        swap (i, n - 1, arr);
      } else {
        swap (0, n - 1, arr);
      }
    }
    generateNoRepeats(n - 1, arr, result);
  }
  
  return result;
}

function permAlone(str) {
  var inputArr = str.split("");
  var result = [];
  
  return generateNoRepeats(inputArr.length, inputArr, result).length;
}

permAlone('aab');

#5

Another non-recursive solution using Heap’s algorithm…
Code Explanation:: Read comments…


function permAlone(str){
var strLen = str.length;
var arr = str.split("");
var c = [];
var counter = 0;

// Function to swap array’s variables’ content.
function swap(idx1, idx2) {
var tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
};

for (var i = 0; i < strLen; i ++){
c[i] = 0;
};

//Check the 1st string for repeated consecutive characters.
if (!/(.)\1+/g.test(str)) counter += 1;

// Generate arrays of permutations using the Heap’s non-recursive algorithm.
//https://en.wikipedia.org/wiki/Heap%27s_algorithm
var i = 0;
while (i < strLen){
if (c[i] < i){
if (i % 2 === 0) swap(0, i);
else swap(c[i], i);
//Check repeated consecutive characters and increment the counter for unique strings.
if (!/(.)\1+/g.test(arr.join(""))) counter += 1;
c[i] += 1;
i = 0;
} else {
c[i] = 0;
i += 1;
}
}
return counter;
}


#7

Puh, it might be fast, but it’s long! 300 lines!
It looks like you use shortcuts when it’s clear that certain patterns have repeated characters. Dare to explain?


#8

Here’s mine, probably of no use regarding speed but it’s nice and short. It’s recursive but in a different way than suggested above.

function permAlone(str) {
  var re=/(.)\1/;
  function pT(p,o){
    if(o.length){
      var sum=0;
      for(var i=0;i<p.length+1;i++){
        sum+=pT(p.slice(0,i).concat(o[0]).concat(p.slice(i)),o.slice(1));
      }
      return sum;
    }
    else return !re.test(p.join(''));
  }
  return pT([],str.split(''));
}

#9

Indeed it is pretty long ^^

It looks like you use shortcuts when it’s clear that certain patterns have repeated characters.

You are right.

Let’s say i have this string : str = "aaaabbbccdf"
First i will look at all the repeating letters.
There are 4 ‘a’, 3 ‘b’, 2 ‘c’.
If there are no repeating letters, the answer is simply str.length! = 11! = 39916800.

Now i take the first group of repeating letters, “aaaa”, i will not take into consideration any of the other letters, and call them “x”.
"aaaaxxxxxxx"
from it, i will build any of the strings which possibly have no repeating letters :
“axaxaxaxxxx”
“axaxaxxaxxx”

“xxxxaxaxaxa”

I call these string “form”, because they account for a particular form of the strings, a pattern (really i am not good with words…).
I know that each of these forms, account for 120960 possibilities :
I took the 11! possibilities i had, and divided it by the numbers of possibilities to place the 4 ‘a’ in the string, that is : (11)! / (C(11, 4)) = 120960

Now i don’t know what happen with the ‘x’, so i will have to take each of these forms, to see how much correct strings they contain, let imagine i want to calculate the number of correct strings in this form : "axaxaxaxxxx"
First i will replace the ‘a’ by ‘|’, “|x|x|x|xxxx” (it will represent the fact that there are separations between the letters)
Now i will look at my second group of repeating letters, the 3 ‘b’, and i will do the same thing than with the ‘a’:
“b|b|b|xxxx”
“b|b|x|bxxx”

“x|x|b|xbxb”

I know that each of these forms account for 120960 / C(7, 3) = 3456 possibilities.
And here, if you look the last form “x|x|b|xbxb”, you can see that this form can only contain good strings, you can replace the ‘x’ by whatever letters, you will still have no repeating letters (i call it a perfect form in my program).
So i know i will not have to go further, and i just skipped 3456 possibilities to test for.

I continue like it for each group of repeating letters.

At the end, i know that each “x” will be a different letters, so i don’t need to go further, and i just have to sum everything. :slight_smile:

It is pretty fast because :

  1. I basically skip all the wrong strings. (but that is just like what you can do by improving your program)
  2. More importantly, i add the good strings by big chunk, using “form” which are accounting for a lot of them.

Now i am sure i can still improve it a lot, using symmetry or things like that.
What would be good would be a purely mathematical solution, but i took more time to search for one, that to actually found and program this solution, so i gave up on that.


#11

Oh nice! I was briefly searching for something like what you just wrote but quickly gave up. I’m just a mere physicist, my combinatorics is not at Maths Olympiad level :stuck_out_tongue: What’s your background if I may ask?


#13

hello cambsCoder, I don’t know how you came up with that algorithm but I have to say that it is very impressive. The no repeats please is the last AlGore that I haven’t solved yet and by far the hardest one from FCC in my opinion. I can figure out how to generate permutations, but the hard part is that the combo length is not defined, meaning it needs to adjust itself somehow. I am on day 3 with this one but hopefully an idea will come.


#14

Can’t this problem be solved using formulae? We can find permutations and combinations using formulae involving factorials, right?


#16

Thanks for your inspiration, especially the recursive function call :slight_smile:
I have completed the mission now like below(choose a logical approach, then go through it to the end):


#17

And now for something completely different…

function permAlone(str) {
// want # of occur
var threes = 0;
var twos = 0;
var ones = 0;
var math = 0;

while(str.length>0){
var f = str[0];
var re = new RegExp(f, ‘g’);
var match = str.match(re);
str = str.replace(re,"");
if(match.length > 3){
return 0;
}
else if(match.length === 3){
threes ++;
} else if(match.length === 2){
twos ++;
}
else {
ones ++;
}
}
//now for the math

if (threes=== 0 && twos===0){
math = factorial(ones);
}
if (threes===0 && twos===1){
math = aax(ones);
}
if (threes===0 && twos===2 ){
math = aaxxc(ones);
}
if (threes===1 && twos===1 && ones===0){
math = 12;
}

return math;
}

permAlone(‘aabbcd’);
////////////////////////////////////////////////////////
function aaxxc(num){
if (num === 0){
return 8;
}
else{
var s = 4*(aax(num+1) - aax(num));
return s + num*aaxxc(num-1);
}}

function aax(num){
var s = 2*((factorial(num+1)) - factorial(num));
return s*(num+1)/2;
}

function factorial(num){
var factorial = 1;
if (num < 1) {
return 0;
}
else {
for (i = 1; i <= num; i++){
factorial *= i;
}
return factorial;
}
}


#18

Why does same code work differently on freecodecamp challenge than on repl.it?

I have this code:

//jshint esversion: 6
function permAlone(str) {
  function *permute(a, n = a.length) {
    if (n <= 1) yield a.slice();
    else for (let i = 0; i < n; i++) {
      yield *permute(a, n - 1);
      const j = n % 2 ? 0 : i;
      [a[n-1], a[j]] = [a[j], a[n-1]];
    }
  }
  let perms = Array.from(permute(str.split(''))).map(perm => perm.join(''));
  re = /([a-z])\1{1,}/g;
  console.log(perms);
  matches = 0;
  for(let i=0; i<perms.length; i++){
      if(!perms[i].match(re)){
        matches += 1;
      }
  }
  return matches;
}

permAlone('aab');

on repl.it, it logs six items as expected: [ 'aab', 'aab', 'baa', 'aba', 'aba', 'baa' ]

on freecodecamp.org it logs this instead:

["aab", "aab", "aab", "aab", "baa", "baa", "aba", "aba", "aba", "aba", "baa", "baa"]

And then it on freecodecamp it finds twice as much matches than it should.

Does anyone have any idea why is this happening?:slight_smile:

P.S. This is the first time I see that freecodecamp gives different output than on repl.it.


#19

Please can someone explain why this line is necessary? I’ve been struggling to understand what it does? Would appreciate any help!


#20

This line is calling the swap function and using the conditional (ternary) operator, instead of an IF ELSE statement, to determine the arguments sent to the function. So if “int % 2” evaluates to true (meaning there is a remainder so “int” is an odd number) then “0” is selected, if not then “i” is selected. This logic is part of Heap’s algorithm.


#21

Alright, thanks a lot. I was actually trying to understand why the Algorithm works rather than just implement it. Thanks anyway, I’ll just have to move on for now.


#22

I made another approach that doesn’t rely on Heap’s algorithm and may be easier to understand altough it’s still recursive.
It’s more explained in the comments but it could be formulated as:
For each letter in the string, create arrays of that letter and all of the combinations of the remaining letters.


function permAlone(str) {
  //split the string into an array of letters
  return permNoRepeat(str.split("")).length;
}

function permNoRepeat(chars) {  
  //if 's' contains a single letter, return it
  if (chars.length === 1) {
    return chars;
  }  
  //here we will store all the permutations
  var p = [];
  
  //for every letter in the array
  for (var i = 0; i < chars.length; i++) {
    //create a copy of the array
    var temp = chars.slice();    
    //remove current letter from it
    temp.splice(i,1);
    
    //compute all the permutations of the remaining letters
    var perms = permNoRepeat(temp);
    
    //for each permutation, append the current letter and save it
    for (var j = 0; j < perms.length; j++) {
      //only keep it if the permutation does not start with the current letter
      //to get rid of duplicated consecutive letters 
      //so we append 'a' with 'ba' but not with 'ab'
      if (!perms[j].startsWith(chars[i])) {
        p.push(chars[i] + perms[j]);  
      }        
    }  
  }
  
  return p;  
}

#23

I tried doing it this way. It’s a seventy line code, much longer than most but I hope it’s easy to understand.

var test;

/*
This function is where all other functions are executed
*/
function permAlone(str) {
  var makeArr = [], counter = 0;

  for (var i in str) {
    makeArr.push(str[i]);
  }
  
  test = makeArr.slice(0);
  
  while (counter < str.length - 1) {
    // console.log(makeArr);
    makeArr = makePerms(makeArr);
    counter++;
  }
  
  var regex = /(.)\1+/g;

  var filter = makeArr.filter(function(string) {
  return !string.match(regex);
  });
  
  return filter.length;
}

/*
We call permAlone with a string
*/
permAlone("aba");

/*
This function generates the permutations for each new array
*/
function makePerms(arr) {
  var newArr = [];
  
  for (var j in arr) {
    var array = test.slice(0);
  
    var toJoin = remains(arr[j], array);
    
    for (var k = 0; k < toJoin.length; k++) {
      newArr.push(arr[j] + toJoin[k]);
    }
  }

  return newArr;
}

/*
This function generates the remaining strings to be added into the makePerms string
*/
function remains(string, arr) {
  var array = [];
  for (var j in string) {
    array.push(string[j]);
  }
  
  for (var i in array) {
    var pos = arr.indexOf(array[i]);

    if (pos >= 0) {
      arr.splice(pos, 1);
    }
  }
  var newArr = arr.slice(0);

  return newArr;
}
`

#24

Ohhhh Sh$%^ this one was very tough!!! Going :arrow_upper_left:︎↓←:arrow_lower_right:︎↑ until get this Heap’s algorithm to work!!!

Well after some polishing and making use of some ES6 features I got this:

function permAlone(str) {
  const strArr = [...str];
  const possiblePermuts = [];
  const noRepPermuts = [];
  
  function permuts(n) {
    if (n === 1) {
      possiblePermuts.push(strArr.join(''));
    } else {
      for (let i = 0; i !== n; i++) {
        permuts(n - 1);
        if (n % 2 === 0) {
          [strArr[0], strArr[n - 1]] = [strArr[n - 1], strArr[0]];
        } else {
          [strArr[i], strArr[n - 1]] = [strArr[n - 1], strArr[i]];
        }
      }
    }
  }
  
  permuts(strArr.length);
  
  for (const permut of possiblePermuts) {
    if (!permut.match(/([a-z])(?=\1)/g)) {
      noRepPermuts.push(permut);
    }
  }
  
  return noRepPermuts.length;
}