Count ways to make string with no K consecutive zeroes

Question

Given a string of length N that is made of only 0 and 1's.But some positions of string are '?'.It means their we can put 0 or 1.

Now , the problem is we need to count the number of ways to fill these '?' positions such that No K 0's can be put together.

Like say we have String of length N=4 and string be 0??0

And let K=3 then here we can put '0' at only at max one position out of two.So strings are :

0100
0010
0110

So here answer is 3.Now for given string of length N and K,we need to count number of ways to make this string.

My Approach :

Now am having O(N,K) approach to solve this problem using Dynamic programming in which if we put 0 at ith position than we can put K-1 zeroes in next continous segment of '?' and if we put 1 then we can put K zeroes again.

But N and K can be very large.So is their some better and efficient algorithm ?

Code as mentioned in one of the answers :

int n,k;
cin>>n>>k;
string s;
cin>>s;
s="#"+s;
int size=s.length();

vector<long long int>F(size+1);
F[0]=1;
for(int i=1;i<=size;i++){
    if(s[i]=='R')
    {
        F[i]=0;
    }       
    else if(s[i]=='L'){
        F[i]=1;
    }
    else{
        for(int j=i-1;j>=i-k;j--){
            if(j<0)
            break;
            F[i]=(F[i]+F[j])%MOD;
        }
    }
}
cout<<F[size]<<"\n";

Now Its failing for test case thats a bit bigger.But i ran it on abrute force solution and it didnt matched.

Test case : n=73,k=7 and string s = ???L?R?LLL?L?L?L?LLL???L???RL?????LR?L?LLRL??R???L?RL????RL?R??LL??LLLR?R

The answer should be 877905026.But the code is giving 246470268

Answer 1

HINTS

You could use an array F[n] to count the number of ways of filling positions [0,n) such that there are no K consecutive 0's and there is a 1 at position n-1.

Then to compute F[n+1] based on previous results we know there is a 1 at position n, and between 0 and K-1 preceding zeros. Let the number of zeros be k.

F[0] = 1
F[n] = sum F[n-1-k] for k in 0,1,..,K-1 
   (only including values for k up to where the string at n-1-k is forced to be 1)

This should give the correct answer, but will take time O(NK).

However, we can accelerate the computation of the sum by maintaining a prefix sum for the values of F[n]. In other words, if we store an array S[n]=F[0]+F[1]+F[2]+..+F[n], we can quickly compute a sum over particular indices of F by subtracting two values of S[n].

So by keeping track of the last location of a forced 1 you can then compute the recurrence in O(N).

The final answer will be given by F[N+1].

EXAMPLE 1

For your example of K=3 and a string of 0??0:

F[0] = 1  (Just the empty string)
F[1] = 0 : position n-1=0 is forced to be 0 so no solutions are possible
F[2] = F[1]+F[0] = 1  (Just the string 01)
F[3] = F[2]+F[1]+F[0] = 2 (The strings 001 and 011)
F[4] = 0 : position n-1=3 is forced to be 0 so no solutions possible
F[5] = F[4]+F[3]+F[2] = 3  (the strings 0010 and 0110 and 0000)

So the final answer is 3

EXAMPLE 2

For your second example of 10???0??

F[0] = 1 (empty string)
F[1] = 1 (The string 1)
F[2] = 0
F[3] = F[2]+F[1] = 1 (The string 101)
F[4] = F[3]+F[2]+F[1] = 2 (The strings 1011 and 1001)
F[5] = F[4]+F[3]+F[2] = 3 (10011 and 10111 and 10001)
F[6] = 0
F[7] = F[6]+F[5]+F[4] = 5 (1011001, 1001001, 1001101, 1011101, 1000101)
F[8] = F[7]+F[6]+F[5] = 8 (10110011, 10010011, 10011011, 10111011, 10001011, 10011001, 10111001, and 10001001)
F[9] = F[8]+F[7]+F[6] = 13
           10110011, 10010011, 10011011, 10111011, 10001011, 10011001, 10111001, 10001001
           10110010, 10010010, 10011010, 10111010, 10001010

FIX FOR CODE

Your code is almost correct: with the inner loop changed as below it gives the answer you wanted:

if(s[i]=='R')
{
    F[i]=0;
} else{
    for(int j=i-1;j>=i-k;j--){
        if(j<0)
            break;
        F[i]=(F[i]+F[j])%MOD;
        if (s[j]=='L')
            break;
    }
}