Problem Statement:

Given the integers zero, one, low, and high, we can construct a string by starting with an empty string, and then at each step perform either of the following:

Append the character '0' zero times.
Append the character '1' one times.

This can be performed any number of times.

A good string is a string constructed by the above process having a length between low and high (inclusive).

Return the number of different good strings that can be constructed satisfying these properties. Since the answer can be large, return it modulo 10⁹ + 7.

Example 1:

Input: low = 3, high = 3, zero = 1, one = 1
Output: 8
Explanation: 
One possible valid good string is "011". 
It can be constructed as follows: "" -> "0" -> "01" -> "011". 
All binary strings from "000" to "111" are good strings in this example.

Example 2:

Input: low = 2, high = 3, zero = 1, one = 2
Output: 5
Explanation: The good strings are "00", "11", "000", "110", and "011".

Constraints:

1 <= low <= high <= 10⁵
1 <= zero, one <= low

Solution:

Let us say that for any value of len, the number of strings equal to len statisfying constraints is given by f(len) then we can say that

 
f(len) = f(len-zero) + f(len-one)

This is because to get strings of length len, we can either add zero zeros after strings of length (len-zero) or add one ones after strings of length (len-one). The base case is that f(0)=1 because there is one way to construct strings of length 0 which is the empty string "". Finally to get answer we can sum f(i) for i between low and high inclusive.

Here are 2 examples:

 
Input: low = 3, high = 3, zero = 1, one = 1
f(3) = f(2)+f(2)
f(2) = f(1)+f(1)
f(1) = f(0)+f(0)
f(0) = 1
fvalues = [1,2,4,8]
Answer = 8

Input: low = 2, high = 3, zero = 1, one = 2
f(3) = f(2)+f(1)
f(2) = f(1)+f(0)
f(1) = f(0)
f(0) = 1
fvalues = [1,1,2,3]
Answer = 2+3 = 5

Naive recursion - TLE:

 
class Solution 
{
public:
    int util(int len, int zr, int on)
    {
        if(len<0) return 0;
        if (len==0) return 1;
        return util(len-zr, zr, on) + util(len-on, zr, on);
    }
    int countGoodStrings(int low, int high, int zero, int one) 
    {
        int res = 0;
        for(int i=low; i<=high; i++) res += util(i,zero,one);
        return res;
    }
};

Recursion with memoization (Top Down DP) - AC:

 
class Solution 
{
    int mod = 1e9+7;
    vector<int> memo;
public:
    int util(int len, int zr, int on)
    {
        if(len<0) return 0;
        if (memo[len]!=-1) return memo[len];
        if (len==0) return memo[len]=1;
        return memo[len] = (util(len-zr, zr, on) + util(len-on, zr, on))%mod;
    }
    int countGoodStrings(int low, int high, int zero, int one) 
    {
        memo = vector<int>(high+1, -1);
        int res = 0;
        for(int i=low; i<=high; i++){res += util(i,zero,one); res%=mod;}
        return res;
    }
};

Bottom-up DP - AC:

 
class Solution 
{
    int mod=1e9+7;
public:
    int countGoodStrings(int low, int high, int zero, int one) 
    {
        int res = 0;
        vector<int>dp(high+1,0);
        dp[0]=1;
        for (int i=1; i<=high; i++)
        {
            dp[i] += (i-zero>=0) ? dp[i-zero] : 0;
            dp[i] += (i-one>=0) ? dp[i-one] : 0;
            dp[i] %= mod;
            if (i>=low) res+= dp[i];
            res %= mod;
        }
        return res;
    }
};

Complexity Analysis: TC and SC of both accepted solutions are \(O(n)\).