Remember to use ReadSearchAsk
if you get stuck. Try to pair program and write your own code
Problem Explanation:
This task requires us to return the number of total permutations of the provided string that donât have repeated consecutive letters. It is to be assumed that all characters in the provided string are each unique. For example, aab
should return 2 because it has 6 total permutations (aab
, aab
, aba
, aba
, baa
, baa
), but only 2 of them (aba
and aba
) donât have the same letter (in this case a
) repeating.
To achieve that, weâll have to look at each possible permutation of a string. There are several ways to do that. A common interview question is building a function that collects all permutations of a string. There are several tutorials available on the internet on how to do that.
Potential Methods Used As Solution
Recursive Method
This task can be daunting even after watching a tutorial. To write a recursive solution, you will want to send each new use of the function three inputs:
 A new string (or character array) that is being built.
 A position in your new string thatâs going to be filled next.
 An idea of what characters (more specifically positions) from the original string have yet to be used.
The pseudo code will look something like this:
var str = ???;
permAlone(current position in original string, characters used already in original string, created string) {
if (current string is finished) {
print current string;
} else {
for (var i = 0; i < str.length; i++) {
if (str[i] has not been used) {
put str[i] into the current position of new string;
mark str[i] as used;
permAlone(current position in original string, characters used already in original string, created string);
remove str[i] as used because another branch in the tree for i + 1 will likely use it;
}
}
}
}
permAlone(0, nothing used yet, empty new string (or array the same size as str));
Another way to think about this problem is to start from an empty space. Introduce the first letter to the space. This space will now contain the first subpermutation. Hereâs a diagram illustrating the idea:
NonRecursive Method
// An approach to introduce a new character to a permutation
var ch = '?';
var source = ['?', '?', '?']; // Current subpermutation
var temp, dest = [];
for (var i = 0; i <= source.length; ++i) {
temp = source.slice(0); // Copy the array
temp.splice(i, 0, ch); // Insert the new character
dest.push(temp); // Store the new subpermutation
}
Finding each permutation could then be done nonrecursively by including the above in a function taking a source array and returning a destination array. For each letter of the input string, pass that character, as well as the array returned from the previous call of the function.
A way to visualize this is by considering a tree that starts with the first character of your string:
Relevant Links
Hint: 1
 The easiest way is to use Heapâs algorithm to recursively get a list of all the permutations.
try to solve the problem now
Hint: 2
 Once you have the list then just create a regular expression to catch the repeating characters.
try to solve the problem now
Hint: 3
 You will want to have the permutations as an array of joined strings instead of separated characters.
try to solve the problem now
Spoiler Alert!
Solution ahead!
Basic Code Solution:
function permAlone(str) {
// Create a regex to match repeated consecutive characters.
var regex = /(.)\1+/g;
// Split the string into an array of characters.
var arr = str.split('');
var permutations = [];
var tmp;
// Return 0 if str contains same character.
if (str.match(regex) !== null && str.match(regex)[0] === str) return 0;
// Function to swap variables' content.
function swap(index1, index2) {
tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
// Generate arrays of permutations using the algorithm.
function generate(int) {
if (int === 1) {
// Make sure to join the characters as we create the permutation arrays
permutations.push(arr.join(''));
} else {
for (var i = 0; i != int; ++i) {
generate(int  1);
swap(int % 2 ? 0 : i, int  1);
}
}
}
generate(arr.length);
// Filter the array of repeated permutations.
var filtered = permutations.filter(function(string) {
return !string.match(regex);
});
// Return how many have no repetitions.
return filtered.length;
}
// Test here.
permAlone('aab');
Code Explanation:
 regex contains the regular expression to match repeated consecutive characters.
 The string str is split into an array of characters, arr.
 0 is returned if str contains same characters.
 The function
swap()
is used for the purpose of swapping the contents of two variableâs contents.  The next block of code uses Heapâs algorithm to generate arrays of permutations in permutations.
 The filtered variable filters permutations to include only nonrepeated permutations.

filtered.length
returns the number of total permutations of the provided string that donât have repeated consecutive letters.
Relevant Links
 JS String Prototype Split
 JS String Prototype Match
 JS Array Prototype Push
 JS Array Prototype Join
 JS For Loops Explained
 array.length
 JS Array Prototype Filter
Advanced Code Solution:
function permAlone(str) {
if(str=='') return 1
const bag=new Map()
for(const c of str){
bag.set(c,(bag.get(c)0)+1)
}
const essence=[]
for(let v of bag.values()){
essence[v]=(essence[v]0)+1
}
let fact
{const f=[1]
fact= n=>f[n](f[n]=n*fact(n1))
}
const essL=essence.length
let bits=essL//essence.reduce((s,v)=>s+v,essL)
let bExp=1// essence as a bits expression
let pFact=1, bMask=1
for(let i=0;i<essL && bits<=32;i++){
if(essence[i]==null) essence[i]=0
const v=essence[i]; bits+=v
pFact*= fact(i+1)**v * fact(v)
bExp=bMask; bMask<<=v+1
}
if(bits>32)
throw `Too many bits requiered: ${bits} >32`
bExp+=bMask
// console.log(essence)
// console.log(bExp.toString(2))
class MapA extends Map{
set(key, idx, value){
if(value==null)
return super.set(key, idx),this
let ar=super.get(key)
if(typeof ar!='object')
{ar=[]; super.set(key, ar)}
ar[idx]=value
return this
}
}
let crMap=new MapA()
crMap.set((3<<bitsessL1)1, 0, 1)
for(let lcrM=1;lcrM<str.length; lcrM++){
const nxMap=new MapA()
for(const [key, value] of crMap){
const bDiff=key^bExp,
bnSprout=~((~key&bMask)>>>1 & key),
bnImp=~bDiff&bnSprout,
sum=value.reduce((s,v)=>s+v,0)
let i=0, v=0, allowed=0
for(let crBit=1;crBit&bMask;crBit<<=1){
if(crBit&key) v++; else {i++; v=0}
if(crBit&bnImp) continue
cLabel:{
if(crBit&bDiff)
if(crBit&key)allowed++
else allowed
else break cLabel
if(crBit&bnSprout) continue
}if(allowed)
nxMap.set(key+crBit, i, i?v*sumvalue[i1]:sum)
}
}
//could be done: recycle crMap
crMap=nxMap;
}
return pFact*crMap.get(bExp).reduce((s,v)=>s+v,0)
}
Code Explanation:
The problem asks to Return the number of total permutations
not to generate themâŠPlease follow my Gist for talk and explanations.
Relevant Links
NOTES FOR CONTRIBUTIONS:
 DO NOT add solutions that are similar to any existing solutions. If you think it is similar but better, then try to merge (or replace) the existing similar solution.
 Add an explanation of your solution.
 Categorize the solution in one of the following categories â Basic, Intermediate and Advanced.
 Please add your username only if you have added any relevant main contents. ( DO NOT remove any existing usernames)
See
Wiki Challenge Solution Template
for reference.