Oh wow, now this was a tough algorithm challenge. When I first saw “Map the Debris”, I thought that was going to be the toughest, but it turned out to be a piece of cake compared to “No Repeats Please”.
I’d initally grappled with it for days on end without wrapping my head around it. I finally allowed myself to peek at the guide for it (not the actual code, just the explanation), but even that didn’t help.
The thing that finally cracked it was not thinking about it at all for several weeks, then returning to it with fresh eyes. I still found the guide very useful (especially the tree diagram, really helped to visualize it), but this time it only took me about half an hour to crack it. I guess the mental block last time was just not understanding the concept of recursion very well. I still don’t find it intuitive, but a little easier now.
Even more gratifying was that my solution was slightly shorter than the basic solution in the guide, after removing whitespace and comments from both. It’s also… ahem… more than an order of magnitude slower (and more than two orders of magnitude slower than the advanced solution). Ah well, can’t win 'em all.
My solution
function getAllPerms(inputStr) {
const inputStrArr = inputStr.split('');
const outputArr = [];
function perm(inputArr, outputStr) {
if (inputArr.length === 0) {
outputArr.push(outputStr);
} else {
const len = inputArr.length;
for (let i = 0; i < len; i++) {
const newInputArr = inputArr.slice();
const newOutputStr = outputStr + newInputArr.splice(i, 1);
perm(newInputArr, newOutputStr);
}
}
}
perm(inputStrArr, '');
return outputArr;
}
function permAlone(str) {
return getAllPerms(str).filter(perm => !perm.match(/([\s\S])\1/g)).length;
}
I feel the same way about that algorithm. I have at this point skipped over that algorithm. I will come back to it once I am done with the others and will definitely be using your post as a guide. Thanks for sharing your solution.
This was the toughest challenge for me. It is not so much about the programming skills, as it is about using logic. It took me 6 months to solve this challenge, and until recently I thought I wouldn’t be able to solve it.
My first solution was to make every possible combination of the letters given in the parameter, and then test each combination if it has repeating characters. It worked in every scenario, but it too long for the browser to process it, so freeCodeCamp test console wouldn’t let me get through. It was a bad idea anyway.
Wise men say Some times the best gift is not to get what you want, I believe that’s what happened to me. I decided to leave the problem for a while, and focus on other things. When I returned to the problem, I had a completely different approach. I read the the help that was offered in the challenge, and got an idea on how to solve it.
So this is how it works… Let’s say you are given this parameter string "abcdefa"
First thing is to identify what character appears more than once, since that is what you have to worry about. Here a appears twice, and that helps you calculate the number of permutations you have to substract from total, because you can consider it as one character. The next thing is to see where the pair can occur.
If you have "a b c d e f a"
You can have it appear at the begining of the word:
a a ? ? ? ? ? (factorial of 5 remaining characters)
? a a ? ? ? ? (same as above)
? ? a a ? ? ?
? ? ? ? a a ?
? ? ? ? ? a a
And since the order of letters is important you multiply the number of these calculated permutations with the factorial of the number of characters that can form a pair. Code is longer, but works very fast. Hope this saves somebody’s time
Yeah this is the hardest algorithm. I think you get traumatized with this one. My experience was that I did a solution the first day that worked in chrome but wouldn’t work in the FCC editor because the loop was too long. Then I wracked my brains for another solution that would take less time. That took another day or two so I feel I was lucky with this reading what other people are saying. My solution ended up massive and wasteful, but I think I could make it a lot slimmer if I went back to it. That 6x5x4x3x2x1 thing and drawing a lot of pictures of the patterns the permutations formed were what helped me. I noticed that you could grow the permutations infinitely if you followed a simple rule, so I did that and then swapped the letters in for the numbers and checked if they clashed.
What annoyed me though was that it should be easy to get a set of permutations if you have the right logic. Like when you have seven figures, your starting point should be 7654321 and end point 1234567 and there are 5040 combinations between those. Well, it should be possible to pick a number between 1 and 5040 and with the right logic produce a precise permutation, as if the permutations were a number base that represented the numbers between the two extremes. Anyway, I couldn’t work out how to do that and that was annoying.
I like your code, it’s short and simple. I used recursion too, but instead of dumping all the permutations and then using regex I only went through the ones that did not have duplicate letters and increased the value of a counter. I think this is on ES5 (I started FCC in 2016 but just got to this problem today).
Ahh man, I’m so glad I finally beat this thing. I need a lot of online resources to help wrap my head around this problem.
Anyway, here’s my final solution, after refactoring to check if the string matches my regex pattern during the recursion and not after. Also, after solving, I stopped keeping track of the different patterns since we don’t need them, it’s much less space to just increment a counter. But my solution is recursive, the iterative one was just too difficult for now.
My Solution
const permAlone = str => {
let permCount = 0,
pattern = /(\w)\1/ig,
arr = str.split('');
const swap = (a, b) => {
let temp = arr[a]; arr[a] = arr[b]; arr[b] = temp;
}
const findAllVariations = n => {
if (n == 1 && !arr.join('').match(pattern)) permCount++;
for (let i=0;i<n;i++) {
findAllVariations(n-1);
swap(n % 2 ? 0 : i, n - 1);
}
}
findAllVariations(arr.length);
return permCount;
}
permAlone('abcdefa');
