# Binary Strings of the form *111* [duplicate]

Given an integer $N$, we have to count the number of possible binary strings(string is madeup of only $0$'s and $1$'s) of length $N$, and matches the regular expression pattern $[111]$. For example if $N$ is $4$, then $1110$ , $0111$ , $1111$ are the possibilities.

I have worked on it, and have got the following recurrence:

$\text{count}(a,N) = 4\text{count}(0,N-3) + 2\text{count}(1,N-3)+ \text{count}(2,N-3)$ ; if$(a == 0)$

$\text{count}(a,N) = 2\text{count}(0,N-2)+ \text{count}(1,N-1)$ ; if$(a == 1)$

$\text{count}(a,N) = \text{count}(0,N-1)$ ; if$(a == 2)$

Answer is $[(2^N) - \text{count}(0,N)]$. By using memorization, we can compute the the $\text{count}(0,N)$ in $O(N)$
but is there any better algorithm other than $O(N)$

-

## marked as duplicate by Marc van Leeuwen, William, tomasz, rschwieb, t.b.Sep 15 '12 at 22:10

Probably not: see this answer and the OEIS references cited there. –  Brian M. Scott Sep 7 '12 at 20:51
@BrianM.Scott: do you agree that is a duplicate? –  Ross Millikan Sep 7 '12 at 21:17
@Ross: I’m undecided: it actually does ask a slightly different (and more specific) question, but I doubt that we can come up with a better answer than we had before. –  Brian M. Scott Sep 7 '12 at 21:20
"memorization"? –  Gerry Myerson Sep 7 '12 at 23:12
@Gerry: Are you asking what it means, or do you just want it to be spelled without the "r"? –  Henning Makholm Sep 8 '12 at 1:32

Let $f(N)$ be the number of binary strings of length $N$ that do not contain "111" as a substring. (So you are interested in $2^N - f(N)$.) Every such binary string ends in exactly one of the strings "0", "01", or "011". This gives rise to the recurrence $$f(N) = f(N-1) + f(N-2) + f(N-3),$$ the "tribonacci recurrence". The inital values are $f(1)=1$, $f(2)=2$, and $f(3)=4$. Therefore a closed form can be given that is similar to the one for the tribonacci numbers, but with different constants in front of the exponential terms.