freeCodeCamp Algorithm Challenge Guide: No Repeats Please

no-repeats-please.js

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(n-1))
  }
  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 required: ${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
    }
  }
  const sumOf=arr=>arr.reduce((s,v)=>s+v,0)
  let crMap=new MapA()
  crMap.set((3<<bits-essL-1)-1, 0, 1)
  for(let step=1;step<str.length; step++){
    const nxMap=new MapA()
    for(const [key, value] of crMap){
      const bDiff=key^bExp, 
        bSprout=(~key&bMask)>>>1 & key,
        sum=sumOf(value)
      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&bDiff)
          if(crBit&key)allowed++
            else allowed--
        if(allowed && crBit&bSprout)
          nxMap.set(key+crBit, i, i?v*sum-value[i-1]:sum)
      }
    }
    //could be done: recycle crMap
    crMap=nxMap;
  }
  return pFact*sumOf(crMap.get(bExp))
}

//permAlone('aaab');
console.log(permAlone('abfdefa'))

no-repeats-please.md

freeCodeCamp Algorithm Challenge Guide: No Repeats Please

Relevant Links

• Comment on my GitHub Gist
• The Problem on freeCodeCamp
• 🚀 Run Code

No repeats please

Return the number of total permutations of the provided string that don't have repeated consecutive letters. Assume 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.

Advanced Code Solution

The problem asks to Return the number of total permutations not to generate them. Thus having as input 'abcde' it's well known that the solution is 5! = 1*2*3*4*5 = 120, it's not necessary to generate all 120 possibilities to find out the number 120. Warning: An advanced solution is more friendly with the computer and less with the developer / reviewer / maintainer / tester because of the high level of abstractness.

Let us have another example: 'abfdefa'. For this input I should have the same output as for 'abfdeaf' (swapping the last 2 letters) because the order of the input is meaningless. Knowing this we can extract a more meaning information: {a:2, b:1, f:2, d:1 e:1}

But what if I replace letter a with c, matters? Or if I swap e and f: 'cbedfce' getting {c:2, b:1, f:1, d:1 e:2}, should I get a different response? No. Thus the meaningful information about input is that I have 2 letters that occur twice each and 3 symbols that occur only once each, {1:3, 2:2} or [3,2]. As another example, [3,1,2] means a sequence of 3*1+1*2+2*3 = 11 symbols, 3 unique letters, 1 group of 2 identical letters and 2 groups, each of 3 letters like 'abcddeeefff'. Symbol d1 is different of symbol d2, but as letters are equal. And 'aaab' translates in [1,0,1] or in [1,0,1,0,0] but we will chose not to have 0 as the last element in list (array) for input but striving to get permAlone(input) we'll pass through temporary forms like [1,0,0] or [1,1,0] keeping their length as length of the goal ([1,0,1]).

I define distance of [a,b,c,..] as |[a,b,c,..]| = a+b*2+c*3+.. i.e. the length of the string which represents it.

Let's calculate recursively permAlone([a,b,c,..]). From this string we can choose as the first symbol any kind of letter. permAlone([a,b,c,..]) = a*permAlone([a-1,b,c,..]) + b*2*permAlone([a+,b-1,c,..]) + c*3*permAlone([a,b+,c-1,..]) +.. where [a,b+,c-1,..] is [a,b+1,c-1,..] but restricted to not use as a first symbol any symbol from a specific letter, that one that was of size 3 but now is of size 2. Therefore

permAlone([a,b+,c-1,..])
     = a*permAlone([a-1,b+1,c-1,..]) + b*2*permAlone([a+,b,c-1,..]) + (c-1)*3*permAlone([a,b+1+,c-2,..]) +..
     = permAlone([a,b+1,c-1,..]) - 2*permAlone([a+,b,c-1,..])

As you notice, for any string [a,b,c,..], permAlone([a,b,c,..]) is a combination of strings of length |[a,b,c,..]|-1. Also, but less obvious, permAlone([a,b,c,..]) is divided by a!*b!*pow(2!,b)*c!*pow(3!,c)*.. and permAlone([a,b+,c,..]) is divided by a!*b!*pow(2!,b+1)*c!*pow(3!,c)*..

Recursive proof:

• permAlone([1,0,0]) = 1 which is divided by 1!*0!*pow(2!,0)*.. = 1
• permAlone([a,b,c,..]) = a*X1*(a-1)!*b!*pow(2!,b)*c!*pow(3!,c)*.. + b*2*X2*a!*(b-1)!*pow(2!,b-1)*c!*pow(3!,c)*.. + c*3*X3*a!*b!*pow(2!,b+1)*(c-1)!*pow(3!,c-1)*.. =
. . = a!*b!*pow(2!,b)*c!*pow(3!,c)*.. * (X1+X2+X3+..)
• permAlone([a,b+,c,..]) = permAlone([a,b+1,c,..]) - 2*permAlone([a+,b,c,..]) = X1*a!*(b+1)!*pow(2!,b+1)*c!*pow(3!,c)*.. - 2*X2*a!*b!*pow(2!,b)*c!*pow(3!,c)*.. =
. . = a!*b!*pow(2!,b+1)*c!*pow(3!,c)*.. * (X1*(b+1)-X2)

Knowing this let's make our live easier operating with a striped version of permAlone, named perm

permAlone([a,b,c,..])  = perm([a,b,c,..])  * a!*b!*pow(2!,b  )*c!*pow(3!,c)*..
permAlone([a,b+,c,..]) = perm([a,b+,c,..]) * a!*b!*pow(2!,b+1)*c!*pow(3!,c)*..
and

perm([a,b,c,..]) = perm([a-1,b,c,..]) + perm([a+,b-1,c,..]) + perm([a,b+,c-1,..]) +..
perm([a,b+,..])  = (b+1)*perm([a,b+1,..]) - perm([a+,b,..])
perm([a+,b,..])  = (a+1)*perm([a+1,b,..]) - perm([a ,b,..])

From here we can jump strait to code unless you think in imperative way and want to do more optimizations. My way of optimizing this is to start with the shortest string and step by step to generate and calculate viable forms toward my objective. From a string I can generate more in just one step, on every step increasing the number of strings but being careful not to generate dead end forms.

Let me explain myself by examples: let the target be [3,1,2]; I start with [1,0,0]. In step 2 I generate [2,0,0] and [0,1,0], both with distance 2. From this set of strings of length 2 I generate another one of length 3 (in step 3): [3,0,0] from [2,0,0], [1,1,0] from ([2,0,0] and [0,1,0]), [0,0,1] from [0,1,0]. I will call it sprouting, [2,0,0] sprouts [3,0,0] and a part of [1,1,0], [0,1,0] sprouts the other part of [1,1,0] and [0,0,1]

4. [3,0,0]->([4,0,0], [2,1,0]); [1,1,0]->([2,1,0], [0,2,0], [1,0,1]); [0,0,1]->([1,0,1], but not [0,0,0,1] because is dead end for me which I'm targeting [3,1,2])
5. [4,0,0]->([5,0,0], [3,1,0]); [2,1,0]->([3,1,0], [2,0,1]); [0,2,0]->([1,2,0], [0,1,1]); [1,0,1]->([2,0,1], [0,1,1])
6. ...
7. ... [1,3,0]->([2,3,0], [0,4,0], [1,2,1]); ...
8. ... [1,2,1]->([2,2,1], [0,3,1], [1,1,2]); ...
9. ...
10. ...
11. [2,1,2]->([3,1,2] only); [4,0,2]->([3,1,2] only); [3,2,1]->([3,1,2] only)

[a,b,c] is viable iff c <= 2 and b+c <= 1+2 and a+b+c <= 3+1+2

It's like playing a game with an uni-dimensional board of 3 spaces and 6 pawns. On a space can be any number of pawns, stacked. On every turn I can place a pawn on the board, on the leftmost space or I can move one that's already on the board with one step to the right, promoting it on a higher position. The goal is to bring them in the [3,1,2] formation. Thus I can not pass through [0,4,0] position. I'm not able to demote any pawns, i.e. move it to the left.

But where are the restricted forms, those with + sign?, because I need them in the building of normal forms. I will use two maps, one already built (crMap) and one under construction (nxMap), with a normal form as keys and as corresponding value, an array of numbers, the perms of forms that compose the perm of key, first one normal and the other ones restricted. crMap.get([a,b,c,..])=[perm([a-1,b,c,..]), perm([a+,b-1,c,..]), perm([a,b+,c-1,..]), ..]. I keep only the values because I can figure out the form from key and position in array. If, let's say b is 0, [a+,b-1,c,..] don't exist and crMap.get([a,b,c,..])[1] stay undefined

Building nxMap: Let's suppose that we already know the set of keys of nxMap from crMap. I iterate on this set and for the key [a,b,c,..] I start building nxMap.get([a,b,c,..]):

perm([a-1,b,c,..])=sumOf(crMap.get([a-1,b,c,..]))
perm([a+,b-1,c,..])=(a+1)*perm([a+1,b-1,..]) - perm([a ,b-1,..])
    =(a+1)*sumOf(crMap.get([a+1,b-1,..])) - crMap.get([a+1,b-1,..])[0]
perm([a,b+,c-1,..])=(b+1)*perm([a,b+1,c-1,..]) - perm([a+,b,c-1,..])
    =(b+1)*sumOf(crMap.get([a,b+1,c-1,..])) - crMap.get([a,b+1,c-1,..])[1]
..

A way to build nxMap is to iterate on crMap and for every key in crMap to generate the keys for nxMap and for every new key of nxMap to build the appropriate value. But my way is to iterate on crMap keys and on its value. For every key and index i, I build nxMap.get(key+i)[i], where key+i is the key with key[i]-1 on position i and key[i+1]+1 on next position. The key is the extended form where key[0] is the number of pawns out the board.

Either way you choose you must have a map that see two keys equal by value, not by reference. In JavaScript only primitives​ are compared by value. Hence I must find a translation of a key as an array of natural numbers to a number or if I need more memory, a string primitive. In my code I use a 32 bits int as key. For every space on board I have a 0 bit and for every pawn an 1 bit starting with the pawns out of the board. The lower bits have pawns of lower ranks. [1,3,0] is in reverse order 110101110 and right is 011101011. I used 3+6 bits.

In the sequence of bits I seek from right to left the 1 bit that is followed by a 0. These bits are candidates for promotion or places of key sprouting. In 011101011 the bits are 010001010. If my target is [3,1,2] -> 110101110, one candidate is not accepted, the bit in position 3. For bit 7 on the left of the key are 0 pawns (1 bit) but in target is 1. The bit 3 has 3 pawns as the target, to be accepted must have less than the target on the same position. The bit 1 has 4 and the target has 5.

Because any key and the target have the same number of 1 bits (6) I can count the bits from the right inclusive being 6 - no. 1 bits from the left exclusive. If the difference is 0 the candidate is not accepted.

...

Please write me bellow about what do you think.

Hey !
Great solution and explanation.

permAlone([a,b,c,..]) is divided by

I think you mean "is divisible by"

If am correct, the time complexity of this algorithm is O( (2*sqrt(n))! / (sqrt(n)!)^2 )
I considered a string with sqrt(n) groups of sqrt(n) letters here, I mean by example, for n=25 : "aaaaabbbbbcccccdddddeeeee"

But I am unsure really.

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