⚡Flashcard Drill➔
NeetCode #688LC-2466Medium1-D Dynamic Programming
← Back to All Problems

#688 · #2466 · Count Ways To Build Good Strings(统计构造好字符串的方案数)

📌 Problem Statement & Constraints

Given low, high, zero, and one, build strings by appending either zero copies of the character zero or one copies of the character one at a time. A good string has length in the inclusive range [low, high]. Return the number of distinct good strings modulo 10^9 + 7. Constraints: 1 <= low <= high <= 10^5, 1 <= zero, one <= 10^5.

💡 Core Algorithmic Approaches

  1. Let dp[len] be the number of ways to build a string of exactly length len.
  2. The last append was either a block of zero zeros or a block of one ones, so dp[len] = dp[len - zero] + dp[len - one].
  3. The base case is dp[0] = 1 for the empty string.
  4. Sum dp[len] over len in [low, high] and reduce modulo 10^9 + 7.

💻 Benchmark Python3 Implementation

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
        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
        return sum(dp[low:high + 1]) % MOD

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(high): one pass over the lengths.
💾 Space Complexity
O(high): the DP array.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the modulo: the counts grow exponentially and must be reduced each step.
  • Summing dp[0..high]: only lengths in [low, high] count, and length 0 is not a good string.
  • Treating zero == one as a single transition: when both are equal the two additions both apply, which correctly doubles the count.
  • Off-by-one on the length range: the range is inclusive of high, so the slice ends at high + 1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems