Leetcode 2466. Count Ways To Build Good Strings

Problem

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^9+7$.

Algorithm

Dynamic Programming (DP). Define dp[i] as the number of valid strings of length i that can be formed using the given rules.
$$dp[i]=dp[i-\text{zero}]+dp[i-\text{one}]$$

This is valid if i - zero >= 0 and i - one >= 0.

Code

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        dp = [0] * (high + 1)
        dp[0] = 1
        for i in range(high + 1):
            if i >= zero:
                dp[i] = (dp[i] + dp[i - zero]) % 1000000007
            if i >= one:
                dp[i] = (dp[i] + dp[i - one]) % 1000000007
        
        ans = 0
        for i in range(low, high+1):
            ans = (ans + dp[i]) % 1000000007
        return ans