 # Find the number of binary strings of length N with at least 3 consecutive 1s

we have an integer N, We have to find the number of all possible distinct binary strings of the length N, which have at least three consecutive 1s. So if n = 4, then the numbers will be 0111, 1110, 1111, so output will be 3.

Can anyone have any idea how to use dynamic programming here.
It will be a great help.

DP(1)=DP(2)=0, DP(3)=1 (Obviously)
For general N, The answer can be obtained by 1 of 2 ways:

1. Strings with at least 3 consecutive ones already present before end = 2*DP(N-1), select last index as 0 or 1
2. Strings with no instance of 3 consecutive ones before the end, and the first occurrence coming at the end. So the last 4 characters are 0111, and before that the characters can be anything such that there are no 3 consecutive 1s. So, this is equal to the number of binary strings of length N-4 without 3 consecutive 1s. This can be obtained by the total number of strings of length N-4 minus DP(N-4). i.e. 2^{N-4}-DP(N-4)

Thus DP(N) = 2*DP(N-1) + 2^{N-4} - DP(N-4)

Let’s check this,
DP(4) = 2*DP(N-1) + 2^{N-4}= 2 +1 = 3
DP(5) = 2*DP(4) + 2^{1}-DP(1)= 6+2-0 = 8
and so on.

I hope it’s correct.

1 Like

How this initiution comes in your mind.
From where I should practice these type of questions.
And also suggest any video describing about these.

could you explain a little more how this formula came and how you approach this?

My Intuition
Usually(based on my experience), problems based on counting the number of ways are mostly solved in 2 ways:

1. Directly solved by a combinatorial argument
2. Or Using DP.

Since the OP explicitly mentioned DP (and the problem did not seem anyway trivial for a combinatorial answer), i started thinking in terms of DP.

Ok we want to use DP. What to do now?
That means we need a scheme to construct our solution of a bigger problem using solutions of smaller problems. Now DP can work in many directions, the most obvious direction is that DP(N-1) is solved and we want to solve DP(N), so let’s try that first

Can we write DP(N) using solution of DP(N-1)?

• DP(N) means all strings of length N with at least 3 consecutive ones. DP(N-1) means all strings of length N-1 with at least 3 consecutive ones. Are they related? Are they same? Or are they completely different?
• If we think a bit, by definition, if we take any string in DP(N-1) and append 0 or 1 at the end, it must belong to DP(N). That gives us the first term in my answer i.e. 2DP(N-1).
• Now what other strings belong to DP(N)? We have only counted those strings from DP(N) which have at least 3 consecutive 1s upto N-1. So the only thing that we have not counted is the strings where the first occurence of 3 consecutive 1s happens at the Nth step. Let’s call this C(N)

How to calculate C(N)?
As the first occurence of 3 consecutive 1s happens at the Nth step, it means:

1. the last 3 digits must be 1.
2. It also means that the 4th last digit must be 0 (Why?)
3. Before that the string can be anything as long as it does not have 3 consecutive ones (Why?) (Because the 4th last digit is 0, so if there are no 3 consecutive ones upto the N-4th digit, there is no way we can have 3 consecutive ones before the Nth digit.

So how to calculate the number of strings of length N-4 without 3 consecutive ones?
Wait, we already have the number of strings with 3 consecutive ones. So we can subtract that from the total possible strings of length N-4. i.e. 2^{N-4}-DP(N-4). This completes the answer

Disclaimer
To be honest, there is nothing fancy about this formula or any video. I have not used any special resource, algorithm or data structure for this. These solutions come naturally once you practice more and occasionally test understanding of mathematics.
There is ton of material and problems online about DP. However, the most important part is only how does the intuition come to mind and you don’t need to approach it the same way as I did. Just try to write the solution in terms of any smaller problems and don’t be afraid to try out different approaches. Including some bonus below to stress on that further.

Bonus 1
Talking of different ways to approach the problem. Let’s try the complimentary version. Denote EP(N) as number of strings of length N with at most 2 consecutive ones.
EP(N)=EP(N-1) (append 0 at end) + EP(N-1) (append 1 at the end) - Y where Y is the number of strings of length N where last 3 digits become 111. Again we reach a similar answer
EP(N)=2*EP(N-1)-EP(N-4)
We can verify this by substituting, DP(N)=2^N-EP(N)
After cancelling terms, we get DP(N)=2DP(N-1)-DP(N-4)+2^{N-4}

Bonus 2
Let’s try to attempt this combinatorially. Is it possible to solve it that way?
Usually, when given a problem of counting something with at least K where K is small enough, it’s easier to solve the complimentary problem, of at most K-1, and then subtract it from the total count.
So, the problem reduces to finding strings where at most 2 ones are together. Denote it by P(N,2), i.e. problem of length N, with at most 2 ones together

To get a feel of how it’s possible, let’s look at easier problems first:

1. Strings with maximum 0 ones together.
This is only possible if all elements are 1.
P(N,0)=1

2. Strings with maximum 1 ones together.
This can be handled using stars and bars technique.
Denote S1(N,k) as the number of strings of length N satisfying the condition containing exactly K ones.How to find this?
Note that if N is less than 2k-1, the answer is 0 (by pigeonhole or any argument)
for N=2K-1, the answer is 1, and you can construct this by putting 1 at the start and then alternating between 0 and 1.
So we start from this base case of M=2K-1, and insert the remaining N-M numbers which are zeros using stars and bars technique in the K+1 slots created by these K ones. i.e. S1(N,K) = {N-M+K}\choose{K} = {N-K+1}\choose{K}.
Summing this over all K, we can get P(N,1)

3. Strings with maximum 2 ones together
I offer a construction similar to the one above. First assume K is even. Then if N is less than M=1.5K-1, then there are 0 ways. The base case is M=1.5K-1, where there is only 1 way. (example 11 for K=2, or 11011 for K=4, or 11011011 for K=6) .
Again, we can use stars and bars to insert the remaining N-M numbers which are zeros in the K+1 slots created by these K ones.
so N-M+K choose K, is N-0.5K+1 choose K
We can do a similar argument for odd K, (the expression will be slightly different and is left as an exercise to the reader)
This gives us P(N,2) in order N as well, though the computation involves binomial coefficients, but maybe you can simplify it further.

Bonus 3
Look at this problem that appeared in a contest last week. It uses a slightly similar but different DP and maybe a good exercise.

Moral of the Story?
You can solve problems with lot of approaches. There is nothing like the best approach. Everyone thinks differently. Please don’t be stuck on thinking why you are not able to think the same solution that someone else did. Don’t be afraid to try out different approaches. Identifying the best approach for a problem is usually acquired through lot of practise and editorials

3 Likes

As an additional statement, I would like to point out the following:

DP(N)=2DP(N−1)−DP(N−4)+2^{N-4}
DP(N-1)=2DP(N−2)−DP(N−5)+2^{N-5}
Eliminating the exponential term from these, we get
DP(N)=4DP(N−1)−4DP(N−2) - DP(N-4)+2DP(N-5)

This formulation lets us compute DP(N) in O(logN) time, using matrix multiplication (similar to fibonacci numbers. So if required, we can pass ridiculously large test cases.

3 Likes

since few days i am gaining more knowledge from you i would like to ask question in future by mentioning you in comment ,thank you brother

And again many many thanks for giving time and effort