# 2466. Count Ways To Build Good Strings

## Description

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 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 <= 105
• 1 <= zero, one <= low

## Solutions

Solution 1: Memoization Search

We design a function $dfs(i)$ to represent the number of good strings constructed starting from the $i$-th position. The answer is $dfs(0)$.

The computation process of the function $dfs(i)$ is as follows:

• If $i > high$, return $0$;
• If $low \leq i \leq high$, increment the answer by $1$, then after $i$, we can add either zero number of $0$s or one number of $1$s. Therefore, the answer is incremented by $dfs(i + zero) + dfs(i + one)$.

During the process, we need to take the modulus of the answer, and we can use memoization search to reduce redundant computations.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n = high$.

• class Solution {
private static final int MOD = (int) 1e9 + 7;
private int[] f;
private int lo;
private int hi;
private int zero;
private int one;

public int countGoodStrings(int low, int high, int zero, int one) {
f = new int[high + 1];
Arrays.fill(f, -1);
lo = low;
hi = high;
this.zero = zero;
this.one = one;
return dfs(0);
}

private int dfs(int i) {
if (i > hi) {
return 0;
}
if (f[i] != -1) {
return f[i];
}
long ans = 0;
if (i >= lo && i <= hi) {
++ans;
}
ans += dfs(i + zero) + dfs(i + one);
ans %= MOD;
f[i] = (int) ans;
return f[i];
}
}

• class Solution {
public:
const int mod = 1e9 + 7;

int countGoodStrings(int low, int high, int zero, int one) {
vector<int> f(high + 1, -1);
function<int(int)> dfs = [&](int i) -> int {
if (i > high) return 0;
if (f[i] != -1) return f[i];
long ans = i >= low && i <= high;
ans += dfs(i + zero) + dfs(i + one);
ans %= mod;
f[i] = ans;
return ans;
};
return dfs(0);
}
};

• class Solution:
def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
@cache
def dfs(i):
if i > high:
return 0
ans = 0
if low <= i <= high:
ans += 1
ans += dfs(i + zero) + dfs(i + one)
return ans % mod

mod = 10**9 + 7
return dfs(0)


• func countGoodStrings(low int, high int, zero int, one int) int {
f := make([]int, high+1)
for i := range f {
f[i] = -1
}
const mod int = 1e9 + 7
var dfs func(i int) int
dfs = func(i int) int {
if i > high {
return 0
}
if f[i] != -1 {
return f[i]
}
ans := 0
if i >= low && i <= high {
ans++
}
ans += dfs(i+zero) + dfs(i+one)
ans %= mod
f[i] = ans
return ans
}
return dfs(0)
}