2466. Count Ways To Build Good Strings

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 <= high <= 105
• 1 <= zero, one <= low

Approach 01:

class Solution {
public:
    int MOD = 1000000007;
    vector<int> memo;

    int solve(int low, int high, int zero, int one, int currentLength) {
        if (currentLength > high) {
            return 0;
        }

        if(memo[currentLength] != -1){
            return memo[currentLength];
        }

        int total = 0;

        // Base case: Valid string length
        if (currentLength >= low && currentLength <= high) {
            total = 1;
        }

        // Recursive case: Add zeros and ones
        int left = solve(low, high, zero, one, currentLength + zero);
        int right = solve(low, high, zero, one, currentLength + one);

        total = (total + left + right) % MOD;
        memo[currentLength] = total;
        return total;
    }

    int countGoodStrings(int low, int high, int zero, int one) {
        memo.assign(high+1, -1);
        return solve(low, high, zero, one, 0);
    }
};

class Solution:
    MOD = 10**9 + 7

    def solve(self, low, high, zero, one, currentLength):
        if currentLength > high:
            return 0

        # Memoization check
        if self.memo[currentLength] != -1:
            return self.memo[currentLength]

        # Base case: valid string within the range
        total = 0
        if low <= currentLength <= high:
            total = 1

        # Recursive case: add strings of zeros and ones
        left = self.solve(low, high, zero, one, currentLength + zero)
        right = self.solve(low, high, zero, one, currentLength + one)

        total = (total + left + right) % self.MOD
        self.memo[currentLength] = total  # Store result in memo
        return total

    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        # Initialize memoization table
        self.memo = [-1] * (high + 1)
        return self.solve(low, high, zero, one, 0)

Time Complexity:

• Memoization:
  • Each unique state, defined by currentLength, is computed only once due to memoization.
  • The number of possible states is proportional to \( O(\text{high}) \), where \(\text{high}\) is the maximum allowable length.
• Overall Time Complexity for Recursive Approach:

  The total time complexity is \( O(\text{high}) \), as each state is visited exactly once and operations for each state are \( O(1) \).

Space Complexity:

• Memoization Table:
  • A table of size \( O(\text{high}) \) is maintained to store the results for each state of currentLength.
• Recursive Stack Depth:
  • In the worst case, the recursive stack depth can go up to \( O(\text{high}) \), as each recursive call decreases currentLength by at least 1.
• Overall Space Complexity:

  The total space complexity is \( O(\text{high}) \), combining the memoization table and recursive stack space.

Approach 02:

class Solution {
public:
    int MOD = 1000000007;
    int countGoodStrings(int low, int high, int zero, int one) {
        vector<int> dp(high+1, 0);
        dp[0] = 1;

        for(int length = 1; length <= high; ++length){
            if(length>=zero){
                dp[length] = (dp[length] + dp[length-zero])%MOD;
            }
            if(length>=one){
                dp[length] = (dp[length] + dp[length-one])%MOD;
            }
        }
        int result = 0;
        for(int length=low; length<=high; ++length){
            result = (result + dp[length])%MOD;
        }
        return result;
    }
};

class Solution:
    MOD = 1000000007

    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        # Initialize the dp array
        dp = [0] * (high + 1)
        dp[0] = 1  # Base case: 1 way to create a string of length 0

        # Fill the dp array
        for length in range(1, high + 1):
            if length >= zero:  # Add strings ending with `zero`
                dp[length] = (dp[length] + dp[length - zero]) % self.MOD
            if length >= one:  # Add strings ending with `one`
                dp[length] = (dp[length] + dp[length - one]) % self.MOD

        # Calculate the result for lengths within [low, high]
        result = 0
        for length in range(low, high + 1):
            result = (result + dp[length]) % self.MOD

        return result

Time Complexity:

• DP Calculation:
  • We iterate through all values up to \( \text{high} \) to compute the DP array values.
  • The operations for each value are \( O(1) \), so the total computation is \( O(\text{high}) \).
• Result Calculation:
  • Summing up valid lengths from the DP table requires a single pass over the array, which is \( O(\text{high}) \).
• Overall Time Complexity for DP Approach:

  The total time complexity is \( O(\text{high}) \).

Space Complexity:

• DP Array:
  • The DP array has a size of \( O(\text{high}) \), storing values for all lengths up to \( \text{high} \).
• Overall Space Complexity:

  The total space complexity is \( O(\text{high}) \), as only the DP array is stored.