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:
'0' zero times.'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 <= 1051 <= zero, one <= lowclass Solution {
int MOD = 1000000007;
public int countGoodStrings(int low, int high, int zero, int one) {
int goodStrings = 0;
int memo[] = new int[high + 1];
Arrays.fill(memo, -1);
memo[0] = 1;
for (int i = low; i <= high; i++)
goodStrings = (goodStrings + solve(i, zero, one, memo)) % MOD;
return goodStrings;
}
private int solve(int rem, int zero, int one, int[] memo) {
if (memo[rem] != -1)
return memo[rem];
int goodStrings = 0;
if (rem >= zero)
goodStrings += solve(rem - zero, zero, one, memo);
if (rem >= one)
goodStrings += solve(rem - one, zero, one, memo);
return memo[rem] = goodStrings % MOD;
}
}