Move from brute-force thinking to an efficient approach using dynamic programming strategy.
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 <= lowProblem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Dynamic Programming
3 3 1 1
2 3 1 2
climbing-stairs)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2466: Count Ways To Build Good Strings
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];
}
}
// Accepted solution for LeetCode #2466: Count Ways To Build Good Strings
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)
}
# Accepted solution for LeetCode #2466: Count Ways To Build Good Strings
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)
// Accepted solution for LeetCode #2466: Count Ways To Build Good Strings
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #2466: Count Ways To Build Good Strings
// 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];
// }
// }
// Accepted solution for LeetCode #2466: Count Ways To Build Good Strings
function countGoodStrings(low: number, high: number, zero: number, one: number): number {
const mod = 10 ** 9 + 7;
const f: number[] = new Array(high + 1).fill(0);
f[0] = 1;
for (let i = 1; i <= high; i++) {
if (i >= zero) f[i] += f[i - zero];
if (i >= one) f[i] += f[i - one];
f[i] %= mod;
}
const ans = f.slice(low, high + 1).reduce((acc, cur) => acc + cur, 0);
return ans % mod;
}
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.