2466. Count Ways To Build Good Strings

MediumLeetCode

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.

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^5
• 1 <= zero, one <= low

How to solve the problem

• Optimized Dynamic Programming

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        MOD = 10**9 + 7
        f = [0] * (high + 1)
        f[0] = 1
        result = 0
        for i in range(1, high + 1):
            if i - zero >= 0: # Can append `zero` zeros
                f[i] = (f[i] + f[i - zero]) % MOD
            if i - one >= 0: # Can append `one` ones 
                f[i] = (f[i] + f[i - one]) % MOD
        for i in range(low, high + 1):
            result = (result + f[i]) % MOD
        return result

Complexity

Time complexity: O(high) Space complexity: O(high)