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'zerotimes. - Append the character
'1'onetimes.
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 may be large, return it modulo 10^9 + 7.
Examples
Input: [3,3,1,1]
Output: 8
Input: [2,3,1,2]
Output: 5
Hints
Consider that each step in constructing the string is independent, and the total length of the string is the sum of the lengths added in each step. How can you model this as a dynamic programming problem where `dp[i]` represents the number of ways to construct a string of length `i`?
Think about the recurrence relation for `dp[i]`. How does the choice of appending `'0'` or `'1'` affect the count? Specifically, if you append `'0'` `zero` times, it contributes `zero` to the length, and similarly for `'1'`. How can you express `dp[i]` in terms of `dp[i - zero]` and `dp[i - one]`?
To optimize the solution, notice that the problem involves a range of lengths (`low` to `high`). Instead of computing `dp[i]` for every `i` from `0` to `high`, can you find a way to compute the sum of `dp[i]` for `i` in `[low, high]` efficiently? Consider using prefix sums or sliding window techniques to avoid redundant calculations.
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: