Problem Statement & Formal Recurrence

We are given four integers: low, high, zero, and one ($1 le ext{low} le ext{high} le 10^5$, $1 le ext{zero}, ext{one} le ext{high}$). At each step, starting from an empty string "", we can either:

• Append the character '0' exactly zero times (increasing total length by zero).
• Append the character '1' exactly one times (increasing total length by one).

A string is deemed good if its final length $L$ satisfies $ ext{low} le L le ext{high}$. We must compute the total count of distinct good strings modulo $10^9 + 7$.

The Recurrence Relation

Notice that the exact characters ('0' or '1') do not alter the branching factor; only the lengths added matter. Let $DP[i]$ represent the number of valid ways to construct a string of exact length $i$:

Once all lengths up to high are computed, the final answer is simply the sum of all $DP[i]$ where $ ext{low} le i le ext{high}$, taken modulo $10^9 + 7$:

Tabulation vs. Memoized DFS: Why Cache Locality Matters

Developers often debate whether to use top-down recursion or bottom-up tabulation. Comparing the two approaches exposes critical systems-level trade-offs:

State Transition Pipeline

Optimal Implementations: C++20 and TypeScript

Below are production-ready implementations illustrating the optimal bottom-up tabulation approach:

C++20 Implementation

#include <vector>

class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        constexpr int MOD = 1'000'000'007;
        // dp[i] stores the number of valid strings of length i
        std::vector<int> dp(high + 1, 0);
        dp[0] = 1; // Base case: 1 way to form the empty string

        int totalGoodStrings = 0;

        for (int i = 1; i <= high; ++i) {
            long long ways = 0;
            if (i >= zero) {
                ways += dp[i - zero];
            }
            if (i >= one) {
                ways += dp[i - one];
            }
            dp[i] = static_cast<int>(ways % MOD);

            // Accumulate counts within the [low, high] window
            if (i >= low) {
                totalGoodStrings = (totalGoodStrings + dp[i]) % MOD;
            }
        }

        return totalGoodStrings;
    }
};

Modern TypeScript Implementation

export function countGoodStrings(low: number, high: number, zero: number, one: number): number {
    const MOD = 1_000_000_007;
    // Uint32Array ensures efficient contiguous typed memory
    const dp = new Uint32Array(high + 1);
    dp[0] = 1;

    let totalGoodStrings = 0;

    for (let i = 1; i <= high; i++) {
        let ways = 0;
        if (i >= zero) {
            ways += dp[i - zero];
        }
        if (i >= one) {
            ways += dp[i - one];
        }
        dp[i] = ways % MOD;

        if (i >= low) {
            totalGoodStrings = (totalGoodStrings + dp[i]) % MOD;
        }
    }

    return totalGoodStrings;
}

Mathematical Nuance: Modulo Arithmetic & Overflow Prevention

When accumulating large combinatorial sums, applying the modulo operator ($10^9 + 7$) prevents integer overflow. In languages like C++, adding two 32-bit integers that are already bounded by $10^9 + 7$ can produce a sum up to $approx 2 imes 10^9$, which fits within a signed 32-bit integer (max value $2^{31} - 1 approx 2.147 imes 10^9$). However, using a 64-bit accumulator (long long) or performing immediate modulo reductions eliminates any risk of undefined signed overflow behavior across various compiler architectures.

Complexity Analysis

• Time Complexity: $O( ext{high})$. The algorithm executes a single linear for loop from $1$ to high. In each iteration, it performs at most two array lookups and two additions. For $ ext{high} = 10^5$, this requires only $10^5$ operations, completing in approximately $3$ milliseconds.
• Space Complexity: $O( ext{high})$ auxiliary space to store the tabulation vector of size $ ext{high} + 1$. For $10^5$ elements of 4-byte integers, total memory consumption is under $400 ext{ KB}$, effortlessly residing in modern CPU L2/L3 cache hierarchies.