Codesignal Solution: fibonacciWord

Original Problem

The Fibonacci word sequence of bit strings is defined as:

F(0) = "0"
F(1) = "1"
F(n) = F(n − 1) + F(n − 2) if n >= 2

Where + is the string concatenation operation.

The first few elements are:

Given a number n and a bit pattern p, return the number of occurrences of the bit pattern p in F(n).

Example
For n = 6 and p = "10", the output should be
fibonacciWord(n, p) = 5.
The Fibonacci word for n = 6 is "1011010110110", and the string "10" occurs 5 times in the string "1011010110110".

Input/Output

• [time limit] 4000ms (js)

• [input] integer n

  Guaranteed constraints:
  0 ≤ n ≤ 40.

• [input] string p

  The bit pattern you are looking for.

  Guaranteed constraints:
  0 < p.length ≤ 10⁵.

• [output] integer

  The number of occurrences of the bit pattern p in F(n). It is guaranteed that the answer fits in a 32-bit integer.

Solution

The given recursive definition of the fibonacci word sequence has a complexity of \(O(2^n)\). However, a linearized dynamic programming algorithm can be derived. Taking the first two elements, every successive element concatenates the last two elements:

n0 = "0"
n1 = "1"
n2 = n1 + n0
n3 = n2 + n1
n4 = n3 + n2
n5 = ...

This algorithm can be implemented without recursion already:

function fib(n) {
	a = "0"
	b = "1"
	t = "" + n

	for (; n > 1; n--) {
		t = b + a
		a = b
		b = t
	}
	return t
}

With this function the given table can be reproduced. Now to the interesting part, the counting of the overlapping. Using the derived function above, we could simply loop over the string and count the occurrences of \(p\) at the current position. But with \(n=40\) 165580141 iterations are already needed. So we have a new limiting factor. A better way is to use the point only, where b and a get connected. Looking at the \(P\) last digits of the left string and the \(P\) first digits of the right string - with \(P\) being the length of \(p\) - also prevents double-countings. Using the function above as a template, we can implement this idea as:

function fibonacciWord(n, p) {
  a = "0"
  b = "1"
  c = p == a

  r = 0
  s = 0
  P = p.length - 1

  for (; n > 1; n--) {
    r = s + c
    if (P > 0)
      r+= (b.slice(-P) + a.slice(0, P)).indexOf(p) != -1
    c = s
    s = r

    t = b
    b = b + a
    a = t
  }
  return r
}

Which can be simplified a bit, but unfortunately JavaScript is quite expressive on string slicing and matching, so that the final solution isn't that much shorter:

fibonacciWord = (n, p) => {
  a = "0"
  b = "1"
  c = p == a

  r = 0
  P = p.length - 1

  while (--n) {
    t = r
    r+= c + !!P * (b.slice(-P) + a.slice(0, P)).includes(p)
    c = t

    t = b
    b+= a
    a = t
  }
  return r
}