> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Count Ways To Build Good Strings

> Tested Python solution for LeetCode 2466 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 2466, [Medium](/catalog/medium). Topics: [Dynamic Programming](/catalog/topics/dynamic-programming). [View on LeetCode](https://leetcode.com/problems/count-ways-to-build-good-strings/description/).

Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2466   # by problem number
lcpy gen -s count_ways_to_build_good_strings   # by problem name
```

## 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** `10^9 + 7`.

### Examples

```
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.
```

```
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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/count_ways_to_build_good_strings/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/count_ways_to_build_good_strings/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
MOD = 1_000_000_007


class Solution:
    # Time: O(high)
    # Space: O(high)
    def count_good_strings(self, low: int, high: int, zero: int, one: int) -> int:
        # dp[i] = number of distinct strings of length i buildable from the empty string
        dp = [0] * (high + 1)
        dp[0] = 1
        for length in range(1, high + 1):
            total = dp[length - zero] if length >= zero else 0
            if length >= one:
                total += dp[length - one]
            dp[length] = total % MOD
        return sum(dp[low : high + 1]) % MOD
```

## Complexity

| Time | Space |
| - | - |
| O(high) | O(high) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.