Count Ways To Build Good Strings

How it works

Instead of starting from length 0 and recursing forward, we can build the solution iteratively. For each length i, the number of ways to reach it equals the ways to reach length i - zero (then add zeros) plus the ways to reach length i - one (then add ones). This is similar to the classic coin change problem where we count combinations.

Steps

1. Initialize a DP array where dp[0] = 1 (one way to have an empty string).
2. Iterate through lengths from 1 to high.
3. For each length i, set dp[i] = dp[i - zero] + dp[i - one] (checking bounds).
4. Sum up all dp[i] values for lengths in the range [low, high].
5. Return the sum modulo 10^9 + 7.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Where n is equal to the given high value.

Things to watch for

Forgetting the Modulo Operation

When counting the number of good strings, the result can grow very large. Forgetting to apply the modulo 10^9 + 7 during intermediate calculations leads to integer overflow.

Off-by-One Errors in Range Check

The problem asks for strings with length in the range [low, high] inclusive. A common mistake is using exclusive bounds or checking > high instead of >= high when counting valid strings.

Not Initializing the Base Case Correctly

In the bottom-up DP approach, forgetting to set dp[0] = 1 (representing one way to build an empty string) causes all subsequent values to be zero.

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

        for i in range(1, high + 1):
            dp[i] = (dp.get(i - one, 0) + dp.get(i - zero, 0)) % mod

        return sum(dp[i] for i in range(low, high + 1)) % mod

class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        vector<int> dp(high + 1);
        int mod = 1e9 + 7, res = 0;
        dp[0] = 1;

        for (int i = 1; i <= high; i++) {
            if (i >= zero) dp[i] = (dp[i] + dp[i - zero]) % mod;
            if (i >= one) dp[i] = (dp[i] + dp[i - one]) % mod;
            if (i >= low) res = (res + dp[i]) % mod;
        }
        return res;
    }
};