Count Ways To Build Good Strings

medium dp

Problem

At each step, append either zero '0's or one '1's. Count strings whose final length is in [low, high], modulo 10^9 + 7.

Inputlow = 3, high = 3, zero = 1, one = 1

Output8

Each position has two choices, total 2^3 = 8 strings of length 3.

low

high

zero

one

def count_good_strings(low, high, zero, one):
    MOD = 10**9 + 7
    dp = [0] * (high + 1)
    dp[0] = 1
    ans = 0
    for i in range(1, high + 1):
        if i - zero >= 0:
            dp[i] = (dp[i] + dp[i - zero]) % MOD
        if i - one >= 0:
            dp[i] = (dp[i] + dp[i - one]) % MOD
        if i >= low:
            ans = (ans + dp[i]) % MOD
    return ans

function countGoodStrings(low, high, zero, one) {
  const MOD = 1000000007n;
  const dp = new Array(high + 1).fill(0n);
  dp[0] = 1n;
  let ans = 0n;
  for (let i = 1; i <= high; i++) {
    if (i - zero >= 0) dp[i] = (dp[i] + dp[i - zero]) % MOD;
    if (i - one >= 0) dp[i] = (dp[i] + dp[i - one]) % MOD;
    if (i >= low) ans = (ans + dp[i]) % MOD;
  }
  return Number(ans);
}

class Solution {
    public int countGoodStrings(int low, int high, int zero, int one) {
        int MOD = 1_000_000_007;
        long[] dp = new long[high + 1];
        dp[0] = 1;
        long ans = 0;
        for (int i = 1; i <= high; i++) {
            if (i - zero >= 0) dp[i] = (dp[i] + dp[i - zero]) % MOD;
            if (i - one >= 0) dp[i] = (dp[i] + dp[i - one]) % MOD;
            if (i >= low) ans = (ans + dp[i]) % MOD;
        }
        return (int) ans;
    }
}

int countGoodStrings(int low, int high, int zero, int one) {
    const int MOD = 1'000'000'007;
    vector<long long> dp(high + 1, 0);
    dp[0] = 1;
    long long ans = 0;
    for (int i = 1; i <= high; i++) {
        if (i - zero >= 0) dp[i] = (dp[i] + dp[i - zero]) % MOD;
        if (i - one >= 0) dp[i] = (dp[i] + dp[i - one]) % MOD;
        if (i >= low) ans = (ans + dp[i]) % MOD;
    }
    return (int) ans;
}

Explanation

Building a string here means repeatedly appending a block of zero '0's or a block of one '1's. So the real question is: in how many ways can we reach each total length by stacking these two block sizes? That is a classic counting DP very similar to climbing stairs.

We let dp[i] be the number of ways to build a string of length exactly i. To finish at length i, the last block was either a zero-block (so we came from dp[i - zero]) or a one-block (from dp[i - one]). Adding those two gives dp[i].

We start with dp[0] = 1 (one way to build the empty string), then fill upward. Whenever i lands inside the wanted range, that is i >= low, we add dp[i] into the running answer. Everything is taken modulo 10^9 + 7 so the numbers stay small.

Example: zero = 1, one = 1, range [3, 3]. Each step adds either one character, so dp[1] = 1, dp[2] = 2, dp[3] = dp[2] + dp[2] = 4... actually dp[i] = dp[i-1] + dp[i-1] = 2·dp[i-1], giving dp[3] = 8. Since only length 3 counts, the answer is 8.

Because we sweep lengths from 1 to high just once, the whole thing runs in linear time.

Time: O(high) Space: O(high)