No repeats please. Fail

Tell us what’s happening:
I’m trying to solve this task all day and i got some progress but still fail checking.
Where can i check my code iterating it step by step ?

Your code so far

function permAlone(str) {
let arr = str.split("");
let a = 0;
let c = 1;
let b;
for (let j = 2; j < arr.length + 1; j++){
   c *= j;
}
  
for (let o = 0; o < c; o++){    
for (let s = 0; s < arr.length; s++){
b = arr.splice(s,1).join();
arr.splice(s+1,0,b);
let i = 1;
 if(arr.every((e,i,a) => a[i] !== a[i-1])){
  a++;
};
}
}

return a;
}

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

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 6.1; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/79.0.3945.88 Safari/537.36.

Challenge: No Repeats Please

Link to the challenge:
https://www.freecodecamp.org/learn/coding-interview-prep/algorithms/no-repeats-please

  1. Make array from string - let arr;
  2. In the first loop i determine all possible permutations of string finding factorial of array length number - let o;

3.use let o as condition for second loop to check all possible permutations of the string.
4.inside next loop i’m doing permutations with splice method and checking for not repeating letters in array property every and if returned value is true i increase let a by 1 and go to next permutatioon.

i see that i somehow got over iteration and decreasing let c i almost got all checks passed but it is trying to fit answer to question which is not helpful for understanding. Thanks for your attention.

I believe that if you break the problem into 2 it would be more clear:

  1. Find all permutations of the string
  2. Filter output from step 1 and return length of flittered array

Both are quite essential algorithms to know and to me it makes more sense from learning perspective + it would be much easier to debug

Ok. I paused to solve it by my way becasue i stucked.
Now when i’m trying just to fill array with premutations of string i got it full of the same string despite in console i see that mutation is going in resulted array it passes unchanged

function permAlone(str) {
  let arr = str.split("");
  let b;
  let count = [];
  
for (let s = 0; s < arr.length - 1; s++){
  
  
  b = arr.splice(s,1).join();
  console.log(b);
  arr.splice(s+1,0,b); 
  console.log(arr);
  count.push(arr);
  
  }
  

  return count;
}

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

Back to your OP, here is a site I see posted often to run code line by line:

http://pythontutor.com/javascript.html#mode=edit

What are you expecting to see with console.log(permAlone('abcde')); ?

1 Like

Now i just want to fill array with permutations of string but i got array with the same version of string.
[ [ ‘b’, ‘c’, ‘d’, ‘e’, ‘a’ ],
[ ‘b’, ‘c’, ‘d’, ‘e’, ‘a’ ],
[ ‘b’, ‘c’, ‘d’, ‘e’, ‘a’ ],
[ ‘b’, ‘c’, ‘d’, ‘e’, ‘a’ ] ]

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