Hello,

I have been trying for the past few days to wrap my head around Combinatorics problems and how to reason about them.

At the moment, I have this problem:

Given a binary string of length N (2 <= N <= 1000000) consisting of zeros, ones and ?, where ? stands either for a 0 or for a 1, I need to find out the number of ways in which I get to fill all the ? such that there is not allowed to have K (2<=K<=N) consecutive 1s.

Example:

K=3

1??1

The answer for this case will be 3, as we can have:

1001

1101

1011

but we can not have:

1111

as we would have 3 consecutive ones.

- My solution ideas:

As K is very large, we can’t afford to use a brute-force solution, otherwise we could simply enumerate all the possibilites and filter the ones we didn’t need.

There are 2^(number of ?) possible configurations so possibly we are looking at some form of DP solution and or closed-formula?

I tried to come up with some DP state but, couldn’t think on any good one…

Can someone point me in the right direction? I’d really like to get better at solving these kinds of problems!

Best,

Bruno