Number of good binary strings

Dynamic Programming

52.9% acceptance

Mar 31, 2026

You are given four integers minLength, maxLength, oneGroup and zeroGroup. A binary string is good if it satisfies the following conditions: The length of the string is in the range [minLength, maxLength]. The size of each block of consecutive 1's is a multiple of oneGroup. For example in a binary string 00110111100 sizes of each block of consecutive ones are [2,4]. The size of each block of consecutive 0's is a multiple of zeroGroup. For example, in a binary string 00110111100 sizes of each block of consecutive zeros are [2,1,2]. Return the number of good binary strings. Since the answer may be too large, return it modulo 109 + 7. Note that 0 is considered a multiple of all the numbers.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn good_binary_strings(min_length: i32, max_length: i32, one_group: i32, zero_group: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let max_len = max_length as usize;
    let min_len = min_length as usize;
    let og = one_group as usize;
    let zg = zero_group as usize;
    let mut dp = vec![0i64; max_len + 1];
    dp[0] = 1;
    for i in 1..=max_len {
      if i >= og {
        dp[i] = (dp[i] + dp[i - og]) % MOD;
      }
      if i >= zg {
        dp[i] = (dp[i] + dp[i - zg]) % MOD;
      }
    }
    let mut result = 0i64;
    for i in min_len..=max_len {
      result = (result + dp[i]) % MOD;
    }
    result as i32
  }
}