2466. Count Ways To Build Good Strings

Problem¶

Starting from an empty string, repeatedly append either zero zeros or one ones. Count the distinct strings whose lengths are between low and high, inclusive, modulo \(10^9+7\).

Example: low=2, high=3, zero=1, one=2 produces {"00", "11", "000", "011", "110"} → 5.

Key trick¶

Let dp[i] count constructible strings of length i. Every nonempty string ends with one of the two allowed blocks, so dp[i] = dp[i-zero] + dp[i-one] for valid indices.

Trap¶

Apply the modulus during the DP, not just to the final answer: otherwise, the integers can become enormous. Also, dp[0] = 1 represents the empty starting string.

Why is it interesting?¶

The recurrence counts distinct strings through their unique final block, without constructing any strings.

Python solution¶

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        mod = 10**9 + 7
        dp = [0] * (high + 1)
        dp[0] = 1
        ans = 0

        for i in range(1, high + 1):
            if i >= zero:
                dp[i] += dp[i - zero]
            if i >= one:
                dp[i] += dp[i - one]

            dp[i] %= mod
            if i >= low:
                ans = (ans + dp[i]) % mod

        return ans

Time: \(O(\text{high})\). Space: \(O(\text{high})\).

Comment on my solution¶

Your recurrence and final count are correct. Reduce each dp[i] modulo \(10^9+7\) as you compute it; taking the modulus only at the end creates unnecessarily large integers. Also, dp[i] counts constructible strings of length i, not necessarily good strings when i < low.

# Ideas:
# - it resembles knapsack dp

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        # dp[i] number good strings of length i
        dp = [0] * (high + 1)
        dp[0] = 1 # for empty string
        for i in range(1, high + 1):
            prev_zero = dp[i - zero] if i - zero >= 0 else 0
            prev_one = dp[i - one] if i - one >= 0 else 0
            dp[i] = prev_zero + prev_one
        return sum(dp[i] for i in range(low, high + 1)) % (10**9 + 7)

Solution().countGoodStrings(3,3,1,1)
Solution().countGoodStrings(2,3,1,2)