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<sup>9</sup> + 7
.
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".
Solution: fastest one is using tabulation dynamic programming technique.
int countGoodStrings(int low, int high, int zero, int one) {
int sum[100001];
sum[0] = 1;
for (int i = 1; i <= high; i++)
{
long long sumCur = 0;
if (i >= zero)
sumCur += sum[i-zero];
if (i >= one)
sumCur += sum[i-one];
if (sumCur > 0x3000000000000000ll)
sumCur %= 1000000007;
sum[i] = sumCur % 1000000007;
}
long long sumTotal = 0;
for (int i = low; i <= high; i++)
sumTotal += sum[i];
return sumTotal % 1000000007;
}
Way slower approach is to use a map in your code for memoization, and a recursive DFS method.
class Solution {
public:
int countGoodStrings(int low, int high, int zero, int one) {
map<int, int> dp;
long mod = pow(10,9) +7;
function<int(int)> dfs = [&](int length) -> int{
if( length > high ) return 0;
if(dp.find(length) != dp.end() )
return dp[length];
int count = ( length >= low) ? 1 : 0;
count = (count + dfs(length + zero)) % mod;
count = (count + dfs(length + one)) % mod;
return dp[length] = count;
};
return dfs(0);
}
};