LeetCode 2466 - Count Ways To Build Good Strings

The problem asks us to count the number of "good" strings that can be constructed by repeatedly appending either '0' exactly zero times or '1' exactly one times, starting from an empty string. A string is good if its length lies between low and high inclusive.

leetcodemediumdynamic-programming

LeetCode Problem 2466

Difficulty: 🟡 Medium
Topics: Dynamic Programming

Solution

Problem Understanding

The problem asks us to count the number of "good" strings that can be constructed by repeatedly appending either '0' exactly zero times or '1' exactly one times, starting from an empty string. A string is good if its length lies between low and high inclusive. The output must be returned modulo 10^9 + 7 because the number of good strings can grow very large.

In simpler terms, we are trying to find all sequences of operations that build strings whose lengths are in [low, high], where each operation adds a fixed number of '0's or '1's. The input parameters define the size of these building blocks (zero and one) and the acceptable string length range (low to high). The constraints tell us that low and high can be up to 10^5, so an algorithm that tries to generate all strings explicitly will be too slow. Edge cases include low == high, zero == one, or extremely skewed lengths like zero = 1 and one = low.

The key challenge is counting all valid sequences efficiently without enumerating every possible string.

Approaches

A brute-force approach would attempt to generate all possible strings starting from the empty string and then count those with lengths in [low, high]. This approach is correct in theory because it explores all combinations, but it is infeasible due to exponential growth - the number of sequences grows very quickly with high and the sizes of zero and one.

The optimal approach uses dynamic programming. We can define a DP array dp[i] as the number of good strings of length i. We initialize dp[0] = 1 because there is exactly one string of length 0: the empty string. Then for each i from 1 to high, we consider adding a '0' block of length zero or a '1' block of length one, and increment dp[i] accordingly if the resulting length does not exceed i. Finally, we sum dp[i] for all i between low and high to get the total number of good strings.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(high/ min(zero, one))) O(high) Exponentially enumerates all strings, infeasible for large high
Optimal O(high) O(high) DP counts number of strings by length without explicit enumeration

Algorithm Walkthrough

  1. Initialize a DP array dp of size high + 1 with all elements 0, except dp[0] = 1 to account for the empty string.
  2. Loop through i from 1 to high. For each i:

a. If i >= zero, add dp[i - zero] to dp[i]. This accounts for all strings that can reach length i by appending a block of '0'.

b. If i >= one, add dp[i - one] to dp[i]. This accounts for all strings that can reach length i by appending a block of '1'.

c. Apply modulo 10^9 + 7 to dp[i] to avoid overflow. 3. Initialize a result variable total = 0. Loop through i from low to high and add dp[i] to total, again applying modulo. 4. Return total.

Why it works: At each length i, dp[i] represents the number of valid strings of exactly that length. By using the DP recurrence, we correctly count all sequences of block additions without missing or double-counting any. Summing from low to high ensures we only count good 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  # base case: empty string

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

        total = sum(dp[low:high + 1]) % MOD
        return total

In this implementation, the DP array is used to count the number of strings of each length. We iterate from 1 to high and update the count by considering adding '0' and '1' blocks. Modulo is applied at every step to avoid integer overflow. The final sum of dp[low:high + 1] gives the total number of good strings.

Go Solution

func countGoodStrings(low int, high int, zero int, one int) int {
    MOD := 1000000007
    dp := make([]int, high+1)
    dp[0] = 1

    for length := 1; length <= high; length++ {
        if length >= zero {
            dp[length] = (dp[length] + dp[length-zero]) % MOD
        }
        if length >= one {
            dp[length] = (dp[length] + dp[length-one]) % MOD
        }
    }

    total := 0
    for length := low; length <= high; length++ {
        total = (total + dp[length]) % MOD
    }

    return total
}

The Go implementation follows the same logic as Python. Slices are used instead of arrays. Modulo operations are performed at each step to avoid overflow. Edge cases like low == high are naturally handled by summing the appropriate range.

Worked Examples

Example 1: low = 3, high = 3, zero = 1, one = 1

length i dp[i] calculation dp[i]
0 base 1
1 dp[1-1]+dp[1-1] 2
2 dp[2-1]+dp[2-1] 4
3 dp[3-1]+dp[3-1] 8

Sum from low to high → dp[3] = 8.

Example 2: low = 2, high = 3, zero = 1, one = 2

length i dp[i] calculation dp[i]
0 base 1
1 dp[1-1] 1
2 dp[2-1]+dp[2-2] = 1+1 2
3 dp[3-1]+dp[3-2] = 2+1 3

Sum dp[2] + dp[3] = 2 + 3 = 5.

Complexity Analysis

Measure Complexity Explanation
Time O(high) We iterate through each length from 1 to high, performing O(1) operations per iteration
Space O(high) DP array of size high + 1 is used to store intermediate counts

The algorithm scales linearly with the maximum length, which is feasible given high <= 10^5.

Test Cases

# provided examples
assert Solution().countGoodStrings(3, 3, 1, 1) == 8  # Example 1
assert Solution().countGoodStrings(2, 3, 1, 2) == 5  # Example 2

# edge cases
assert Solution().countGoodStrings(1, 1, 1, 1) == 2  # minimal lengths
assert Solution().countGoodStrings(5, 5, 2, 3) == 2  # exact combination to reach high
assert Solution().countGoodStrings(1, 100000, 1, 1) >= 0  # stress test with large high
assert Solution().countGoodStrings(10, 10, 5, 5) == 2  # multiple ways to reach exact length
Test Why
Example 1 Simple case where low=high and zero=one=1
Example 2 Small range with different zero and one values
Minimal lengths Ensures base case handling of empty string
Exact combination Tests ability to match length exactly using blocks
Large high Ensures algorithm efficiency for maximum constraints
Multiple ways Validates that multiple sequences contribute correctly

Edge Cases

One important edge case is when low == high. Here, the sum is over a single length, so the DP must correctly compute that exact length. Another edge case occurs when zero or one is equal to low - we must correctly handle the situation where only one addition of a block reaches the minimum good length. Finally, extremely skewed values like `zero =