No Repeats Please, challenge

No Repeats Please, challenge
0.0 0

#1

I’m currently working through the Advanced Algorithm Scripting, and after many hours of banging my head against the wall, I was able to complete No Repeats Please. This one has been by far the most difficult for me. At first I thought there must be some correlation between the total characters and the number of repeating characters. It seemed to work at first, take (“aab”) = 6 total perms and 2 non-repeating ones, so 1/3 and (“aabc”) = 24 perms and 12 non-repeating ones (1/2). However this quickly falls apart with stings like (“aabb”) and (“abcdefa”). So I gave up on trying to find an easy mathmatical solution and desided to just generate all possible perms. Sounded a lot easier then it was. It ended up taking me hours to figure out an algorithm that would allow me to generate all perms regardless of length.
Anyways I ended up using a recursive function that is very slow for larger strings, but it works. So I would love to get some feedback on my code and maybe see how others have completed this.
Thanks in advance :slight_smile:

function rotateArr(arr,from) //move the value at 'from' to the end of 'arr' { var a = arr.splice(from,1); arr.push(a[0]); }

var sameAs = [];
var count = 0;

function compare(arr)
{
//Convert array to string
var str=arr.toString();
str=str.replace(/,/g,""); //Remove ,
for(var i=0;i<sameAs.length;i++){
str=str.replace(sameAs[i][0],sameAs[i][1]);//Replace the numbers that represent dups with chars
}
for(var i=0;i<sameAs.length;i++){
if(str.match(""+sameAs[i][1]+sameAs[i][1])!==null){ return; } //Look for any chars that appear twice in a row
}
count++; //if none found increase count
return;
}

function recPerm(arr,len)
{
var cpy=arr.slice(0);
//Create a copy of the passed in array to ensure we do not change the original
for(var i=0;i<len;i++)
{
if(len>3){ recPerm(cpy,len-1); }
else
{
compare(cpy);
rotateArr(cpy,cpy.length-2); //swap last two
compare(cpy);
rotateArr(cpy,cpy.length-2); //Restore last two
}
rotateArr(cpy,cpy.length-len);
}
}

function permAlone(str)
{
if(str.length===1){ return 1; }
var skip=false;
//Ensure all global variables are reset
count = 0;
sameAs = [];
//Fill in ‘sameAs’ array with format [index#,“char”]
for(var i=0;i<str.length-1;i++)
{
skip=false;
for(var b=i+1;b<str.length;b++)
{
if(str[i]===str[b])
{
if(!skip){ sameAs.push([""+i,str[i]]); skip=true; }
sameAs.push([""+b,str[b]]);
}
}
}
var baseArray = [];
//Create an Array of numbers the same length as out string
//This will be used to ensure that every char has a unique value
for(var i=0;i<str.length;i++){ baseArray.push(i); }
//Call recursive function to walk through all possible permutations
recPerm(baseArray,str.length);
return count;
}

permAlone(‘aab’);


#2

It’d be a lot easier to read if you linked your codecamp page, or a jsfiddle with your code.


#4

@P1xt
Thanks for the example. I just discovered the wiki page for this and it looks like your used a similar algorithm to the one there. Did you use that to help you figure this one out? I also was wondering why you use ‘let’ instead of ‘var’. Is there some advantage to this?


#6

I really liked this one, and everyone seems to miss two very big ideas when they solve this algorithmically, so im cross posting this to a few of these threads.

1. When you are forming each permutation, and you come across one that has repeating letters, you do not need to keep going.

this is the difference between only going through a handful of steps to solve the test case ‘aaaaaaaa’, or finding 40320 permutations just to filter every single one out afterwards.

2. You are asked to return a number, not a list. Storing an array of thousands of strings is unnecessary.

You dont actually need the list of strings, you just need to keep track of how many you find. This is only possible when you keep (1) in mind.

You can think of the problem in this way:

How many unique routes can I take through a string, without passing through identical letters consecutively?

Then you can set up a much simpler algorithm to traverse the letters of a string and count how many times it can successfully get through the entire string without hitting the same letter twice.

This is one possible solution using these two ideas:

function permAlone(s,p){

  return s.split('').reduce(
    (x,y,i)=> y==p ? x : s.length==1? 1 : x + permAlone(s.slice(0,i) + s.slice(i+1),y) ,0);
  
}

.