No Repeats Please -- Stuck on Last test

No Repeats Please -- Stuck on Last test
0.0 0

#1

Before I begun this challenge I did a google search on fastest algorithm to calculate permutations and came across the Heap’s Algorithm and after reading the wikipedia on this algorithm I decided to not use it because I didn’t want to generate !n array elements and then start comparing each array for repeated characters side-by-side. No Thanks - too brute force I thought. I wanted a more mathematical approach and long story short I came across this mathematical approach on StackOverflow.

I found Lulai’s explanation to be one I could understand the best… As a programmer, I try to understand the problem (the subject matter) before I write code. So here’s my code and where I need help is with calculating the OVERLAPS on the last test case, If anyone else used this same approach, I hope you can point me in right direction. Thank you.

function permAlone(string) {
	'use strict';
  var arr = string.split('');
  var letters = arr.length;
  var repeats = [], uniq = 1, permutations;
  
  arr.sort();
  
  var getFactorial = function (num) {
    
    var fNum = false;
    if ( num === 0 ) { num = 1; } // 0! = 1 is special case.

    fNum = num;
    while ( --num > 0 ) {
      fNum *= num;
    }
    return fNum;
  }; 
  
  // count repeated letters 
  for (var j = 0, r = 1; j < letters; j++) { 

    if ( j !== letters-1 ) {
      if ( arr[j] !== arr[j+1] ) {
        
        // count unique letters
        uniq++; 
        
        // save count of any previous letter repeats
        if ( r > 1 ) {
          repeats.push(r);
          r = 1;
        }
      }
      else {
        r++;
        continue;
      }
    }
    // save count of any previous letter repeats 
    if ( r > 1 ) {
      repeats.push(r);
      r = 1;
    }   
    
  } // end for
  
  // Check for special cases
  if ( repeats.length && uniq === 1 ){ // 'string of the same letter'
    permutations = 0;
  } 
  else if ( ! repeats.length && uniq === 1 ){ // 'string of one letter'
    permutations = 1;
  }
  else {
    permutations = getFactorial(letters);

    // Reduce Permutations by subtracting out invalid permutations that contain repeated letters.
    // Add to Permutations any overlap of invalid permutations that were counted during another repeatedLetterSet
 
    var  k = 0, repeatedLetterSets = repeats.length, invalids = 0;
    while ( repeatedLetterSets && k < repeatedLetterSets ) {
    
      // 1st getFactorial() gets #ofBoxes where repeated letters may appear
      // 2nd getFactorial() gets repeated letters Factorial. ie. 'aa' = !2, 'aaa' = !3.
 
      var repeatCount = repeats[k];
      while ( repeatCount >= 2 ) {
        invalids = getFactorial( letters - repeatCount +1 ) * getFactorial( repeatCount );
        permutations -= invalids;
        repeatCount-- ;
      }  
      // add back in overlap of where repeated characters were counted over again with multiple
      // repeated characters sets. ie [aabb]
      if ( repeats.length > 1 ) {
        permutations += getFactorial ( letters - repeats.length ) * getFactorial( repeats[k] );
      }      
      k++;
    }
  }
  return permutations;
}

#2

People may be less likely to help you if they have to go searching for the challenge you’re referring to in your question. You should use the “ask for help” button from within the challlenge so we have the information we need:

Also, you’ll get more help if you categorize your post as help. This post is currently uncategorized.


#3

Thanks. In the end I resolved this on my own. Modified my overlaps calculation to:

      // add back in overlap of where repeated characters were counted over again with multiple
      // repeated characters sets. ie [aabb]
      if ( repeats.length > 1 ) {
        overlaps = getFactorial ( letters - repeats[k] ) * getFactorial( repeats[k] );
        permutations += overlaps;
      }