Leetcode2466.CountWaysToBuildGoodStrings

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 1 0 9 + 7 10^9 + 7 109+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. d p [ i ] = d p [ i − zero ] + d p [ i − one ] dp[i] = dp[i - \text{zero}] + dp[i - \text{one}] dp[i]=dp[i−zero]+dp[i−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