No repeats please. Fail

Ahhh its one of those …problems :slight_smile:

Take a look at this recent post. It’s a um …head to keyboard thing.

This problem used to be on the advanced algorithms section of the old FCC curriculum. I can understand why it’s been moved to a non-essential section of the new curriculum. It is very difficult to solve if you approach it in the wrong way.

The approach you are taking involves generating all possible permutations and then checking them to see if they are valid. You should not take this approach as your code will time out. The test case "zzzzzzzz" will have 8! (40320) possible permutations alone, which you are then nesting with additional loops. The iterations will quickly balloon making the execution time too long.

Instead, the problem is solvable using an inner recursive function with a global counter. The idea is that the recursive function builds up the string permutations but stops as soon as two consecutive characters are the same. If a string can be fully built with no consecutive repeats then the global counter can be incremented. At the end the global count is returned. This approach will dramatically reduce the number of iterations your code has to make.

1 Like

But how would you know the next character without performing permutation? Don’t you still need same n! operation just to know the next character? I’m a bit lost…

The solution I am proposing would only check all permutations in a worst case scenario, where all the characters are different (e.g. "abcde").

The permutations are built up and checked one character at a time. As soon as two consecutive characters are found to be the same, the calculations for that particular set of permutations can cease as none will satisfy the condition of no repeats.

This can be achieved through a recursive function, which generates the permutations and only calls itself again if the current character being examined is different from the previous one. If this works for the full length of the string permutation then the global count can be incremented, as the string is confimed to have no consecutive repeats.

I can post my solution if you’re interested.

No no, it’s ok… I can more or less imagine how it works and will still stand on:

:slight_smile:

I found all possible permutations of a string with not very gloomy algorithm which i found on stackover though something wrong with my resulted array because it has no length and so can’t be iterated

function permAlone(string) {

  if (string.length < 2) return string;
  
  let permutations = []; 

  for (var i = 0; i < string.length; i++) {
    var char = string[i];

    if (string.indexOf(char) != i) continue;

    var remStr = string.slice(0, i) + string.slice(i + 1, string.length);

    for(var elem of Array.from(permAlone(remStr))){
      permutations.push(char + elem);
    }
  
  }
  return permutations;
}

console.log(permAlone('aadcrb'));

All arrays have length and could be iterated. Here are couple remarks regarding algorithm:

function permAlone(string) {
  // you might want to return [string] instead for consistency
  if (string.length < 2) return string;
  let permutations = []; 

  for (let i = 0; i < string.length; i++) {
    const char = string[i];
    
    // This line makes no sense and this statement will never be true
    if (string.indexOf(char) != i) continue;

    // No need to do string.slice(i + 1, string.length), just string.slice(i + 1) would be enough
    const remStr = string.slice(0, i) + string.slice(i + 1, string.length);

   // permAlone returns either String or Array, both iterable with for-of loop, so there is no need for Array.from() method here
    for(let elem of Array.from(permAlone(remStr))){
      permutations.push(char + elem);
    }
  
  }
  return permutations;
}

If you fix remarks it would be perfect permutation algorithm, the one you shall memorize :slight_smile:

2 Likes

It is not working

function permAlone(string) {

  if (string.length < 2) return [string];
  
  let permutations = []; 

  for (let i = 0; i < string.length; i++) {
    var char = string[i];

  
    let remStr = string.slice(i + 1);

    for(let elem of permAlone(remStr)){
      permutations.push(char + elem);
    }
  
  }
  return permutations;
}

console.log(permAlone('aadcrb'));
// The remark was only about the second part
const remStr = string.slice(0, i) + string.slice(i + 1);

Sorry, but permutations.length still shows 0 and permutations[0] = aa

Did you try it like this?

const permutations = permAlone('abba');
console.log(permutations.length);

Ok, i did it though i still don’t understand what exactly it changed but where i have to implement regex checking of permutations. Now it is not working because of same problem with array

let a = 0;
let reg = /(.)\1+/;

permutations.forEach(function(elem, i){
    if(elem[i].match(reg)) a++;
  })

What elem in forEach() refers to?

It has to refer to each string in array but it can’t because array behaves itself in non-clear to me way

Right, so if it refers to each element of the array - string, what elem[i] refers to then?

1 Like

Ok, it is just elem.match(reg) but where i need to put it? It is not working inside function permAlone
return a shows

TypeError: permAlone(...)[Symbol.iterator] is not a function

and same with

const a = permAlone('abba');
console.log(a);

Think if you can use different method instead of forEach() for filtering permutations

Hint: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/filter

Ok, finally i got right answers though only outside the function. If i do

function permAlone(string) {
  
  if (string.length < 2) return [string];
  
  let permutations = []; 

  for (let i = 0; i < string.length; i++) {
    var char = string[i];

    let remStr = string.slice(0,i) + string.slice(i + 1);

    for(let elem of permAlone(remStr)){
      permutations.push(char + elem);
    }
  }

let reg = /(.)\1+/;
let a = permutations.filter(elem =>
    !elem.match(reg),
  );
  return a; //a.length here returns TypeError: permAlone(...)[Symbol.iterator] is not a function
}
const a = permAlone('abfdefa');
console.log(a.length);//a.length here returns 2640

Can anyone say what do i need to change in my last code so that would work?