Mid/SeniorDynamic Programming
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 can be large, return it modulo 10^9 + 7.
Example 1
Input
low = 3, high = 3, zero = 1, one = 1Output
8All binary strings from "000" to "111" are good strings in this example.
Example 2
Input
low = 2, high = 3, zero = 1, one = 2Output
5The good strings are "00", "11", "000", "110", and "011".
Constraints
- 1 <= low <= high <= 10^5
- 1 <= zero, one <= low