# Count Ways To Build Good Strings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-ways-to-build-good-strings)
Canonical: https://scaleengineer.com/dsa/problems/count-ways-to-build-good-strings
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Companies:** [Citadel](https://scaleengineer.com/companies/citadel)
---
## 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 <= high <= 105`
* `1 <= zero, one <= low`

# Approaches
## Top-Down Dynamic Programming with Memoization
This approach uses recursion to solve the problem by breaking it down into smaller, overlapping subproblems. To avoid the exponential time complexity of naive recursion, we use a memoization table (an array) to store the results of subproblems once they are computed. The number of ways to form a string of a certain length is the sum of the ways to form the strings from which it could have been created in the last step.
**Time:** O(high) - Each state `solve(i)` for `i` from 0 to `high` is computed only once due to memoization. The main loop runs `high - low + 1` times, and each call to `solve` will trigger computations that fill the memo table up to `high` in total. · **Space:** O(high) - This is for the memoization array of size `high + 1` and the depth of the recursion stack, which can also go up to `high` in the worst case.
**Pros:** It's a direct translation of the recurrence relation, which can be more intuitive to formulate.; It only computes the states that are actually needed to reach the target lengths.
**Cons:** Can have higher constant overhead due to recursive function calls compared to an iterative solution.; In some languages or environments with strict recursion depth limits, it could theoretically lead to a stack overflow error for very large inputs, though this is not an issue for the given constraints (`high <= 10^5`).
### Explanation
The problem has optimal substructure and overlapping subproblems, making it a perfect candidate for dynamic programming. We can define a function, `count(length)`, which calculates the number of ways to construct a string of a given `length`.

A string of `length` can be formed by either:
1.  Appending `zero` '0's to a valid string of length `length - zero`.
2.  Appending `one` '1's to a valid string of length `length - one`.

This gives us the recurrence relation: `count(length) = count(length - zero) + count(length - one)`. The base case is `count(0) = 1`, representing the single empty string. If `length < 0`, the number of ways is 0.

A naive recursive implementation would be very slow. We optimize this by using a memoization array, `memo`, to cache the result for each length. The main logic then involves calling this memoized recursive function for each length from `low` to `high` and summing up the results, taking the modulo at each step.

```java
class Solution {
    int MOD = 1_000_000_007;
    int[] memo;

    public int countGoodStrings(int low, int high, int zero, int one) {
        memo = new int[high + 1];
        java.util.Arrays.fill(memo, -1);
        
        int totalWays = 0;
        for (int length = low; length <= high; length++) {
            totalWays = (totalWays + solve(length, zero, one)) % MOD;
        }
        return totalWays;
    }

    private int solve(int length, int zero, int one) {
        if (length == 0) {
            return 1; // Base case: one way to form an empty string
        }
        if (length < 0) {
            return 0; // Impossible to form a string of negative length
        }
        if (memo[length] != -1) {
            return memo[length]; // Return cached result
        }

        // Recurrence relation
        int ways = (solve(length - zero, zero, one) + solve(length - one, zero, one)) % MOD;
        
        memo[length] = ways; // Cache the result
        return ways;
    }
}
```
### Algorithm
- 1. Define a constant `MOD = 10^9 + 7`.
- 2. Create a memoization array `memo` of size `high + 1` and initialize it with a sentinel value (e.g., -1) to indicate that a state has not been computed.
- 3. Define a recursive helper function, let's call it `solve(length)`, that computes the number of ways to build a string of the given `length`.
- 4. Inside `solve(length)`:
  - If `length == 0`, return 1 (base case for the empty string).
  - If `length < 0`, return 0 (impossible to form).
  - If `memo[length]` is not the sentinel value, it means we have already computed this subproblem, so return `memo[length]`.
  - Otherwise, recursively calculate the result using the recurrence: `ways = (solve(length - zero) + solve(length - one)) % MOD`.
  - Store the computed result in `memo[length]` before returning it to avoid re-computation.
- 5. In the main function, initialize a variable `totalWays = 0`.
- 6. Iterate from `length = low` to `high`. In each iteration, call `solve(length)` and add the result to `totalWays`, taking the modulo to keep the sum within the integer limits.
- 7. Return `totalWays`.

## Bottom-Up Dynamic Programming
This is an iterative approach that builds the solution from the ground up, which is often more efficient than its recursive counterpart. We use a DP array to store the number of ways to form strings of each possible length, starting from length 0 and iterating up to `high`. This avoids recursion and its associated overhead.
**Time:** O(high) - The first loop runs `high` times to populate the DP table. The second loop runs `high - low + 1` times. The total time complexity is dominated by the first loop, making it proportional to `high`. · **Space:** O(high) - We use an array of size `high + 1` to store the DP states.
**Pros:** Generally more efficient in practice than the top-down approach due to the lack of recursive call overhead.; Guaranteed not to cause a stack overflow.; The iterative logic is often considered cleaner and easier to reason about for tabulation-style DP.
**Cons:** It computes the number of ways for all lengths up to `high`, even if some are not strictly necessary (e.g., if `low` is large). However, these smaller lengths are required to compute the larger ones, so this is not a significant drawback.
### Explanation
We can solve this problem iteratively using a dynamic programming array, let's call it `dp`, of size `high + 1`. The value `dp[i]` will store the number of ways to construct a string of length exactly `i`.

The base case is `dp[0] = 1`, representing the single empty string which has a length of 0.

We then iterate from `i = 1` up to `high`. To calculate `dp[i]`, we consider the two ways a string of length `i` could have been formed in the final step:
1.  By appending `zero` '0's to a string of length `i - zero`. The number of ways to do this is `dp[i - zero]`. This is only possible if `i >= zero`.
2.  By appending `one` '1's to a string of length `i - one`. The number of ways to do this is `dp[i - one]`. This is only possible if `i >= one`.

Thus, the state transition is `dp[i] = (dp[i - zero] + dp[i - one]) % MOD`. After filling the `dp` array, the total number of 'good' strings is simply the sum of `dp[i]` for all `i` in the range `[low, high]`.

```java
class Solution {
    public int countGoodStrings(int low, int high, int zero, int one) {
        int MOD = 1_000_000_007;
        int[] dp = new int[high + 1];
        dp[0] = 1; // Base case: one way to form an empty string

        for (int i = 1; i <= high; i++) {
            // Number of ways to form a string of length i
            if (i >= zero) {
                dp[i] = (dp[i] + dp[i - zero]) % MOD;
            }
            if (i >= one) {
                dp[i] = (dp[i] + dp[i - one]) % MOD;
            }
        }

        int result = 0;
        for (int i = low; i <= high; i++) {
            result = (result + dp[i]) % MOD;
        }

        return result;
    }
}
```
### Algorithm
- 1. Define a constant `MOD = 10^9 + 7`.
- 2. Create a DP array `dp` of size `high + 1` to store the number of ways to form a string for each length.
- 3. Initialize the base case: `dp[0] = 1`, as there is one way to form an empty string (by doing nothing).
- 4. Iterate with a loop variable `i` from 1 to `high`.
- 5. Inside the loop, calculate `dp[i]` using the recurrence relation:
  - `ways = 0`
  - If `i >= zero`, it means we can form a string of length `i` by appending `zero` '0's to any string of length `i - zero`. So, add `dp[i - zero]` to `ways`.
  - If `i >= one`, similarly, add `dp[i - one]` to `ways`.
  - Set `dp[i] = ways % MOD`.
- 6. After populating the `dp` array, initialize a variable `result = 0` to store the final count of good strings.
- 7. Iterate from `i = low` to `high`, and for each `i`, add `dp[i]` to `result`, taking the modulo at each addition.
- 8. Return `result`.

# Solutions
### Java

```java
class Solution {
private
  static final int MOD = (int)1 e9 + 7;
private
  int[] f;
private
  int lo;
private
  int hi;
private
  int zero;
private
  int one;
public
  int countGoodStrings(int low, int high, int zero, int one) {
    f = new int[high + 1];
    Arrays.fill(f, -1);
    lo = low;
    hi = high;
    this.zero = zero;
    this.one = one;
    return dfs(0);
  }
private
  int dfs(int i) {
    if (i > hi) {
      return 0;
    }
    if (f[i] != -1) {
      return f[i];
    }
    long ans = 0;
    if (i >= lo && i <= hi) {
      ++ans;
    }
    ans += dfs(i + zero) + dfs(i + one);
    ans %= MOD;
    f[i] = (int)ans;
    return f[i];
  }
}

```

### CPP

```cpp
class Solution {
public:
  const int mod = 1e9 + 7;
  int countGoodStrings(int low, int high, int zero, int one) {
    vector<int> f(high + 1, -1);
    function<int(int)> dfs = [&](int i) -> int {
      if (i > high)
        return 0;
      if (f[i] != -1)
        return f[i];
      long ans = i >= low && i <= high;
      ans += dfs(i + zero) + dfs(i + one);
      ans %= mod;
      f[i] = ans;
      return ans;
    };
    return dfs(0);
  }
};

```

### Python

```python
class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int: @ cache def dfs(i): if i > high: return 0 ans = 0 if low <= i <= high: ans += 1 ans += dfs(i + zero) + dfs(i + one) return ans % mod mod = 10 ** 9 + 7 return dfs(0)

```