Count ways to build good strings

Dynamic Programming

59.0% acceptance

Feb 25, 2026

2220

210

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_good_strings(low: i32, high: i32, zero: i32, one: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let h = high as usize;
    let z = zero as usize;
    let o = one as usize;
    let l = low as usize;
    let mut dp = vec![0i64; h + 1];
    dp[0] = 1;
    let mut ans = 0i64;
    for i in 1..=h {
      if i >= z { dp[i] = (dp[i] + dp[i - z]) % MOD; }
      if i >= o { dp[i] = (dp[i] + dp[i - o]) % MOD; }
      if i >= l { ans = (ans + dp[i]) % MOD; }
    }
    ans as i32
  }
}