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 109 + 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&nbsp;<= high&nbsp;<= 105

• 1 <= zero, one <= low

Solution

/**
 * @param {number} low
 * @param {number} high
 * @param {number} zero
 * @param {number} one
 * @return {number}
 */
var countGoodStrings = function(low, high, zero, one) {
    var mod = Math.pow(10, 9) + 7;
    var dp = new Array(high + 1).fill(0);
    dp[0] = 1;
    for (var i = Math.min(zero, one); i <= high; i++) {
        if (i >= zero) {
            dp[i] = (dp[i] + dp[i - zero]) % mod;
        }
        if (i >= one) {
            dp[i] = (dp[i] + dp[i - one]) % mod;
        }
    }
    var res = 0;
    for (var i = low; i <= high; i++) {
        res = (res + dp[i]) % mod;
    }
    return res;
};

Explain:

dp[i] means, for string length i, has dp[i] kinds of different good strings.

dp[i] = dp[i - zero] + dp[i - one]

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).