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
- Let
dp[len]be the number of ways to build a string of exactly lengthlen. - The last append was either a block of
zerozeros or a block ofoneones, sodp[len] = dp[len - zero] + dp[len - one]. - The base case is
dp[0] = 1for the empty string. - Sum
dp[len]overlenin[low, high]and reduce modulo10^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 == oneas 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 athigh + 1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.