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.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3

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

Solution

Method 1 - Using Dynamic Programming

To solve this problem, we can use dynamic programming (DP). We’ll define a DP array dp where dp[i] represents the number of ways to construct a good string of length i.

For each length i from low to high, we can build on previous results:

  • If we append '0' zero times to a string of length i-zero, it’ll form a good string of length i.
  • If we append '1' one times to a string of length i-one, it’ll form a good string of length i.

We’ll sum up all the dp values from low to high to get our final answer.

Approach

  1. Define DP Array:
    • Initialize a DP array dp of size high + 1 with all zeros, except dp[0] which is 1 because there’s one way to construct a string of length 0 (the empty string).
  2. Fill DP Array:
    • Iterate over each length from 1 to high.
    • For each length, add the counts where:
      • length >= zero from dp[length - zero].
      • length >= one from dp[length - one].
  3. Result Calculation:
    • Sum up all values in dp from low to high.
  4. Modulo Operation:
    • Apply modulo 10^9 + 7 at each step to ensure the result fits within limits.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public int countGoodStrings(int zero, int one, int low, int high) {
        final int MOD = 1_000_000_007;
        int[] dp = new int[high + 1];
        dp[0] = 1;  // Base case: one way to construct a string of length 0
        
        for (int length = 1; length <= high; length++) {
            if (length >= zero) {
                dp[length] += dp[length - zero];
            }
            if (length >= one) {
                dp[length] += dp[length - one];
            }
            dp[length] %= MOD;
        }
        
        // Sum the number of good strings from length low to high
        int ans = 0;
        for (int length = low; length <= high; length++) {
            ans = (ans + dp[length]) % MOD;
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def countGoodStrings(self, zero: int, one: int, low: int, high: int) -> int:
        MOD = 10**9 + 7
        dp = [0] * (high + 1)
        dp[0] = 1  # Base case: one way to construct a string of length 0
        
        for length in range(1, high + 1):
            if length >= zero:
                dp[length] += dp[length - zero]
            if length >= one:
                dp[length] += dp[length - one]
            dp[length] %= MOD
        
        # Sum the number of good strings from length low to high
        ans = sum(dp[low:high + 1]) % MOD
        
        return ans

Complexity

  • ⏰ Time complexity: O(high), where high is the upper bound of the string length. We process each length up to high.
  • 🧺 Space complexity: O(high), due to the storage required for the DP array.