Count Ways To Build Good Strings

lcpy gen -n 2466   # by problem number
lcpy gen -s count_ways_to_build_good_strings   # by problem name

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.

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

MOD = 1_000_000_007


class Solution:
    # Time: O(high)
    # Space: O(high)
    def count_good_strings(self, low: int, high: int, zero: int, one: int) -> int:
        # dp[i] = number of distinct strings of length i buildable from the empty string
        dp = [0] * (high + 1)
        dp[0] = 1
        for length in range(1, high + 1):
            total = dp[length - zero] if length >= zero else 0
            if length >= one:
                total += dp[length - one]
            dp[length] = total % MOD
        return sum(dp[low : high + 1]) % MOD