No Repeats Challenge

I get that this is a very difficult challenge. I’m resolved to finding the error in my code. I like my code because it doesn’t use regexp or an array of possible repeated characters. It just uses math.

I pass all test except for “aaab” and I cannot figure out why. I’m very close to solving this problem in what appears to be a unique way based on what I’ve read on the internet and even here at FCC.

My code seems to fail when a character is repeated 3 times. It works for more than one repeated character and, as I said, passes all tests except for “aaab”.

I’d appreciate your insights.


function permAlone(str) {
  var arr=str.split("");
  var totalChars=arr.length;
  //console.log(totalChars);
  var test;
  var dup=[];
  var currDupChar="";
  var prevDupChar="";
  var dupCharArr=[];
  var total=0;
  var invalid=1;
  var overlaps=1;
  var actPerm=0;
  //console.log("dupchararr=", dupCharArr);
  console.log(arr.sort());
  checkDuplicateChar(arr.sort());
  function checkDuplicateChar(testArr) {
    test= testArr.filter(function(val, index) {
      prevDupChar=currDupChar;
      currDupChar=val;
      //console.log("prevDupChar=", prevDupChar,"currDupChar=", currDupChar);
      if(prevDupChar===currDupChar) {
        //console.log("Array Length=", dupCharArr.length);
        //console.log("dupCharArr[x]=", dupCharArr[dupCharArr.length-1]);
        dupCharArr[dupCharArr.length-1] += 1;
      } else {
        dupCharArr.push(1);
      }
      if (dup.indexOf(val) === -1) {
        dup.push(val);
      }
      return testArr.indexOf(val) !==index;
    });
  }
  //console.log(test);
  // var nonDups=dupCharArr.filter(function(val) {
  //   return val===1;
  // });
  //console.log("nondups=", nonDups);
  dupCharArr= dupCharArr.filter(function (val) {
    return val>=2;
  });
  // console.log("dupCharArr=", dupCharArr);
  // var numDups=dupCharArr.reduce(function (acc,val) {
  //   return acc+val;
  // },0);
  // console.log("numDups=", numDups);
  // console.log("2*nonDups.length+1=", 2*nonDups.length+1);
  // if(2*nonDups.length+1<=numDups) {
  //   console.log("not enough nonDups");
  //   test=0;
  //   console.log(test);
  //   return test;
  // }
  // console.log("dup=", dup);
  console.log("dupCharArr=",dupCharArr);
  var test1=permutations(totalChars,dup,dupCharArr);
  function permutations(numChars,duplicateCharArr,duplicatesPerCharArr) {
    // actualPerm=Total-Invalid+Overlaps
    // calculate Total
    function factorial (x) {
      if (x===0) {
        return 1;
      } else if (x>0) {
        return x * factorial(x-1);
      }
    }
    total=factorial(numChars);
    console.log("total=", total);
    if (duplicatesPerCharArr.length===0) {
      return total;
    }
    for (i=0; i<duplicatesPerCharArr.length; i++) {
      var littleInvalid= factorial(duplicatesPerCharArr[i])/(factorial(duplicatesPerCharArr[i]-1));
      console.log("littleInvalid=", littleInvalid);
      invalid= invalid * littleInvalid;
    }
    invalid=invalid * factorial(numChars-1);
    console.log("invalid=", invalid);
    // overlaps
    if (duplicatesPerCharArr.length>1) {
      for (i=0; i<duplicatesPerCharArr.length; i++) {
        var littleOverlaps=factorial(duplicatesPerCharArr[i])/(factorial(duplicatesPerCharArr[i]-1));
        overlaps= overlaps * littleOverlaps;
      }
      overlaps=overlaps * factorial(numChars-2);
      console.log("overlaps=", overlaps);
    } else {
      overlaps=0;
    }
  }
  actPerm=total-invalid+overlaps;
  console.log("actPerm=", actPerm);
  if (actPerm<0) {
    console.log("actPerm is less than zero: ", actPerm);
    actPerm=0;
  }
  console.log(actPerm);
  return actPerm;

}

permAlone('aaab');

thanks in advance.

This might sound harsh, so you decide whether to take it or not.

You might think you almost solved the problem because you passed all sample tests except for one; however, you are more wrong than you think. The failure is not restricted to some character repeating 3 times. For example, given an input ‘aab’, your function returns 2 where it should’ve been 1. And given an input ‘aabb’, your function returns 8 where it should’ve been 2. Unless you’ve intentionally designed your algorithm to solve subset of the problem, your algorithm design is fundamentally wrong. And, I doubt the problem is you mis-translating your mathematical thought to code

You said your code only uses math, so it seems like you came up with some form of math formula. So here’s my question, what does your formula produce given ‘aaab’, ‘aabb’ and ‘aabc’? If your formula yields correct answer, I’ll promise you to go through over your code and find the problem. Right now there’s just no point in me trying to find any logic error in your code because it is very hard to read and reason about. You will have to expose methodology behind your algorithm.

Thanks for the comments but you have to know that the free code camp solution for “aab” is in fact 2 and the solution for “aabb” is 8. My code passes all FCC tests except for one.

i genuinely believe the difference ( 2 vs 1, or 8 vs 2) is because the problem statement specifies that each duplicate character is “unique” whereas most solutions you’ll find assume that any “a” for example is no different than any other “a”. While I don’t necessarily like the specifications in the FCC problem statement, they are, in fact, the problem I must solve.

Oh actually you are right i’m terribly sorry for the mistake. I’ll look into the problem. Like you said I was mistakenly looking for unique non repeating sequence.

I’ve adjusted my algorithm to fit the FCC spec and your problem is still not restricted 3 consecutive characters. Your algorithm will return 0 for ‘aabbcc’ which is far off from the correct answer 240. So I’m still curious to know what sort of math that you are using because there is something fundamentally wrong with the math that you are using.

Ill update you once I find what you are doing wrong.

So I did some checking and here’s my observation.

Starting with things that I don’t understand

  1. definition of ‘invalid’
  2. definition of ‘overlaps’
  3. your generalization for actPerm = total - invalid + overlaps

About your code

  1. var ‘test’, ‘test1’, is never used, why do they exist?
  2. name of var ‘dup’ is misleading because it also contains non-duplicated element. i.e) given ‘aaab’, it end up with [‘a’ , ‘b’]
  3. 2nd parameter of permutations(), ‘duplicateCharArr’, is never used.
  4. 2nd parameter of permutations(), ‘duplicateCharArr’ has misleading name, it conceptually conflicts with dupCharArr.
  5. Too many nested functions, and most of them rely on unnecessary side effects e.g) checkDuplicateChar(), permutations()
  6. add var keyword in your for loop.

About your logic
Your code functions as you would expect-- there is no errors in execution of your logic. This means your math is not working out. The algorithm is incorrect with following examples:

  1. like you said, any sequence that has a character repeating more than 2 times.
  2. any sequence that has 3 or more varying repeating characters. e.g) ‘aabbcc’, ‘aabbccdd’…

I’ve also tried hard to find math formula that will solve the problem without evaluating each permutation but I’ve failed to do so. I’ve found several factors that affect the result:

  1. number of characters
  2. number of each duplicated characters
  3. character variations

But I haven’t found any connection among them.

My code does solve the problem but it has complexity of, roughly, O(!n) which is pretty bad.
Well, that’s pretty much all I can say. Good luck on working this out mathematically.

an excellent explanation of “total”, “invalid” and “overlaps” is found here:

Let me work through the rest of the list of comments/questions. But I highly recommend reading Lurai’s explanation at link above.

Great now we can talk on the same page, I’ll examine this and try to come up with working code

He’s trying to use the permutation mathematical technique which is very reasonable.
I didn’t use this technique, I brute forced it. When I ran the code, I noticed that ‘aaab’ doesn’t generate any overlap which isn’t possible considering the number of repeated characters there are in the string.

It outputs total = 24, invalid = 18, but no overlaps.

could be totally off base here but the overlaps accounts for over-subtracting cases where there was a case of one element repeated wherein another element was also repeated. So, it appears to me that there is no overlap in this case since there is only one element repeated.

So what that tells me is my logic /math is flawed.

I’ve spent most of the day trying to figure out why “aaab” doesnt’ work. I’ve mapped out the permutations, and as you would expect, there are 24 possible, and all 24 are “invalid”. So that means, I’m not correctly counting invalids.

Or, I’m even more out to lunch than I thought.

here’s my best coherent thoughts right now:

There are 6 permutations where aa occurs, followed by b then a
There are 6 permutations where an a occurs, followed by b, followed by aa
there are 6 permutations where aaa occurs followed by b
there are 6 permutations where b followed by aaa occurs.

now if I could describe that mathematically, I’m home free.

@Cowwy

Yea I can see that now. Anyway, OP’s example ‘aaab’ only have single repeated character ‘a’ so it shouldn’t have any overlap based on the math from the link. So, OP’s code is not wrong about it.

Since you said the technique is very reasonable, I’m wondering if you could help me to understand the formula. How does this formula work with ‘aabbcc’? There’s probably something that I’m doing wrong because I don’t have full grasp on this.

This is my understanding with ‘aabbcc’ which gives incorrect answer.
permutations = 6! = 720
invalid_permutations = 3 * ( 5! * 2! ) = 3 * (240) = 720
overlaps = 3! * 2! * 2! * 2! = 6 * 8 = 48
result = 720 - 720 + 48 = 48
But correct result is 240.

@gobees
This is part of the comment from your link which addresses ‘aaab’ input. I’m sure you’ve already seen it and you’ve found some issues with it.

Case #1 :

…Then, you have some invalid perm. with the three ‘a’ in the same box (AAAB and BAAA) multiplied by the permutations of the 3 ‘a’, which are 6 (total 12)…

|aaa| b => 2! * 3! = 12

Case #2:

…You also have to add all the invalid perm. in which you place two ‘a’ in the same box. Those are 3x2x1 = 12…

(There is a calculation error that states 3x2x1 = 12 but I think the author forgot to put extra 2)
|aa| a b => 3* 2! = 12

My issue with this is that we surely do get overlaps from case#2 such as ‘aaab’. ‘baaa’. So, as soon as we add them back the result is incorrect.

What is your thought on this? And have you tried to apply the formula with ‘aabbcc’?

@gunhoo93
To your post here:
This is my understanding with ‘aabbcc’ which gives incorrect answer.
permutations = 6! = 720
invalid_permutations = 3 * ( 5! * 2! ) = 3 * (240) = 720
overlaps = 3! * 2! * 2! * 2! = 6 * 8 = 48
result = 720 - 720 + 48 = 48
But correct result is 240.

I’m thinking overlaps is too low (as you suspect also) as the math for overlaps to me seems to only consider those cases where all three elements are 'paired together, such as AA paired with BB paired with CC. I think it’s missing the math for AA paired with say BB where the two C’s are not paired together. Such as CAABBC, and also considering something like ABBCCA and so on. Haven’t figured out how to solve it.

as you all have probably learned by now, there is no problem I can find on the internet that addresses the case where each repeat is unique.

On my list of things to try however, when I have more time, is can I find a problem that works with numbers, and the challenge of the problem is say “456” in any permutation is valid or invalid. Because this type of problem is the same problem FCC is asking me to solve, only it’s using unique repeat letters instead of number groups such as the one I’ve postulated above.

re-read of Lurai’s post in stackoverflow shows this for “aaab”

When you have some character repeated more than twice, you must take into account all the grouping possibilities when counting invalid permutations. In ‘aaab’, the total number of perm. is 24. Then, you have some invalid perm. with the three ‘a’ in the same box (AAAB and BAAA) multiplied by the permutations of the 3 ‘a’, which are 6 (total 12). You also have to add all the invalid perm. in which you place two ‘a’ in the same box. Those are 3x2x1 = 12. So, we have 12 invalid perm. with groups of 3, plus 12 invalid perms. with groups of 2. Total - Invalid = 24 - (12 + 12) = 0 – Lurai May 19 '16 at 17:52

So there is apparently no more elegant way than to subtract the case of 3a’s all together and subtract then the permutations where only 2a’s are together.

Next step is to apply this logic to AAABB.

@gobees
That is exactly what I’ve presented to you in my previous reply.
There is a problem with this; calculating individual invalid permutations for each of ‘|aaa| b’ and ‘|aa| ab’ will create overlaps. And, once the overlaps are handled the calculation yields incorrect result.

ok. I don’t think there are overlaps when you strictly count the invalids as Lurai explains for an element that repeats more than 2 times.

Anyway, I put this code together and it passes the tests. I doubt it’s usefulness in the future because I doubt there will be many applications looking at two A’s for example and considering each unique. but who knows.

This was, by far, the hardest problem yet.

Anyway, here’s the code:


function permAlone(str) {
  var arr=str.split("");
  var totalChars=arr.length;
  var dup=[];
  var currDupChar="";
  var prevDupChar="";
  var dupCharArr=[];
  var total=0;
  var invalid=0;
  var overlaps=0;
  var actPerm=0;
  console.log(arr.sort());
  checkDuplicateChar(arr.sort());
  function checkDuplicateChar(testArr) {
    test= testArr.filter(function(val, index) {
      prevDupChar=currDupChar;
      currDupChar=val;
      if(prevDupChar===currDupChar) {
        dupCharArr[dupCharArr.length-1] += 1;
      } else {
        dupCharArr.push(1);
      }
      if (dup.indexOf(val) === -1) {
        dup.push(val);
      }
      return testArr.indexOf(val) !==index;
    });
  }
  dupCharArr= dupCharArr.filter(function (val) {
    return val>=2;
  });
  console.log("dupCharArr=",dupCharArr);
  var test1=permutations(totalChars,dup,dupCharArr);
  function permutations(numChars,duplicateCharArr,duplicatesPerCharArr) {
    // actualPerm=Total-Invalid+Overlaps
    // calculate Total
    function factorial (x) {
      if (x===0) {
        return 1;
      } else if (x>0) {
        return x * factorial(x-1);
      }
    }
    total=factorial(numChars);
    console.log("total=", total);
    if (duplicatesPerCharArr.length===0) {
      return total;
    }
    var dupMagnitude= dupCharArr.reduce(function (acc,val) {
      if (val > acc) {
        acc=val;
      }
      return acc;
    }, 0);
    for (i=0; i<duplicatesPerCharArr.length; i++) {
      var littleInvalid=0;
      if (dupMagnitude===2) {
        littleInvalid=factorial(duplicatesPerCharArr[i]) * factorial(numChars-1);
        invalid= invalid + littleInvalid;
      } else {
        littleInvalid=2*factorial(numChars-1) * factorial(duplicatesPerCharArr[i]-1) + factorial(2) * factorial(duplicatesPerCharArr[i]);
        invalid=invalid + littleInvalid;
        console.log("3: ", littleInvalid);
        return;
      }
      console.log("littleInvalid=", littleInvalid);
    }
    console.log("invalid=", invalid);
    // overlaps
    var littleOverlaps=0;
    if (dupMagnitude===2) {
      overlaps=1;
      if (duplicatesPerCharArr.length>1) {
        for (i=0; i<duplicatesPerCharArr.length; i++) {
          littleOverlaps=factorial(duplicatesPerCharArr[i]);
          overlaps= overlaps * littleOverlaps;
        }
        overlaps=overlaps * factorial(numChars-2);
        console.log("overlaps=", overlaps);
      } else {
        overlaps=0;
      }
    } else if (dupMagnitude===3) {
console.log("Im here");
      // count # of two repeats
      littleOverlaps=factorial(numChars-1) * factorial(dupMagnitude-1) * 2;
            console.log("littleOverlaps=",littleOverlaps);
      // count three repeats
      littleOverlaps=littleOverlaps + factorial(dupMagnitude) * factorial(dupMagnitude -1);
            console.log("littleOverlaps=",littleOverlaps);
      overlaps=littleOverlaps;
    }
  }

  actPerm=total-invalid+overlaps;
  console.log("actPerm=", actPerm);
  if (actPerm<0) {
    console.log("actPerm is less than zero: ", actPerm);
    actPerm=0;
  }
  console.log(actPerm);
  return actPerm;
}
permAlone('aaabb');

It passes small amount of test samples given by FCC but, still, there are many edge cases.

  1. aaabbcc
  2. aaabbccd
  3. aabbcc
  4. abcccd
  5. aaabbb
  6. ,

Plus, I think the example for ‘aaab’ does create overlaps.
Permutations from ‘|aaa| b’ does include 'aaab’
Permutations from ‘|aa| a b’ also include 'aaab’
There’s already one overlap. So you need to add it back but then the result for ‘aaab’ is not zero.

And also, when ‘aaab’ is fed to your algorithm, it calculates 36 invalid permutations and you are jumping to a conclusion that actPerm is 0. Invalid permutations exceeding total permutations already suggest that there should be overlaps during the calculation of invalid.