I want to reply to the No Repeats Please challenge with my solution. My implementation is different from the posted solutions and does not involve generating all possible permutations of the string.
My Solution
I found a solution that only requires a dictionary of: key = character
, value = number of times each was used in the string
(i.e. {"a": 2, "b": 3}
). It directly computes the permutations while also dropping any permutations where there would be sequentially repeated characters previousLetter = currentLetter
function permAlone(str) {
// get dictionary with keys being the letters and the values being
// the number of times the letter was used
function getLetterCounts(str){
let letterCounts = {};
for (let i = 0; i < str.length; i++){
const letter = str[i];
if (letterCounts.hasOwnProperty(letter)){
letterCounts[letter] += 1;
} else {
letterCounts[letter] = 1;
}
}
return letterCounts;
}
// count permutations of the letters that do not count the permutation when
// the previous letter and current letter are the same
function countNonRepeatingStrings(letterCounts, previousLetter) {
let permCount = 0; // need to multiply numbers so start with 1
if (Object.keys(letterCounts).length === 0){
return 1;
}
for (const [currentLetter, count] of Object.entries(letterCounts)) {
let newLetterCounts;
if (currentLetter === previousLetter){
continue;
}
if (count === 1){
newLetterCounts = Object.assign({}, letterCounts)
delete newLetterCounts[currentLetter];
} else {
newLetterCounts = Object.assign({}, letterCounts);
newLetterCounts[currentLetter] -= 1;
}
permCount += count * countNonRepeatingStrings(newLetterCounts, currentLetter);
}
return permCount;
}
const letterCounts = getLetterCounts(str);
// no previous letter to start
return countNonRepeatingStrings(letterCounts, "");
}