Problem Description
Given integers low, high, zero, and one, we need to count the number of different binary strings that can be built by starting with an empty string and repeatedly appending either a block of '0's of length zero or a block of '1's of length one. The resulting string must have a length between low and high (inclusive). Return the total count modulo 10^9 + 7.
Key Insights
- The solution uses dynamic programming to count ways to form strings of various lengths.
- Define dp[i] as the number of ways to form a string of length i.
- Start with dp[0] = 1 (the empty string).
- For each valid length i, update dp[i + zero] and dp[i + one] if they do not exceed high.
- Sum up the results from dp[low] to dp[high] to get the final answer.
- Use modulo arithmetic (10^9 + 7) at every update to keep the numbers manageable.
Space and Time Complexity
Time Complexity: O(high)
Space Complexity: O(high)
Solution
We use a bottom-up dynamic programming approach. A dp array of size high + 1 is initialized with dp[0] set to 1. For each index i from 0 to high, if there is any way to form a string of length i, then:
- Add dp[i] to dp[i + zero] (if i + zero ≤ high).
- Add dp[i] to dp[i + one] (if i + one ≤ high). After processing all indices, we sum the values in dp from index low to high and return the result mod 10^9 + 7.