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:
(x,y,i)=> y==p ? x : s.length==1? 1 : x + permAlone(s.slice(0,i) + s.slice(i+1),y) ,0);