Count Ways To Build Good Strings
Asked at Visa
Problem
Count Ways To Build Good Strings builds strings by repeatedly appending either zero copies of 0 or one copies of 1, and asks how many distinct strings have length between low and high, modulo 10^9 + 7. Only the length matters for counting, so it is Climbing Stairs with two custom step sizes.
Asked At
| Company | Difficulty | |
|---|---|---|
| Visa | Medium | View all Visa questions → |
How to Think About It
Each different sequence of append choices produces a different string, so counting strings = counting sequences of steps.
Key insight: dp[len] = number of strings of exactly that length. Each string of length len ends with either a block of zeros or a block of ones.
Recurrence: dp[len] = dp[len - zero] + dp[len - one] (when those indices are non-negative), with dp[0] = 1.
Sum dp[low..high] for the answer, taking the modulo throughout.
Walkthrough: low = high = 3, zero = one = 1: dp = [1,2,4,8] -> 8 strings.
Optimal Approach
Step 1: dp = [0] * (high + 1), dp[0] = 1.
Step 2: For i from 1 to high:
If i >= zero: dp[i] += dp[i - zero].
If i >= one: dp[i] += dp[i - one].
Take mod.
Step 3: Return sum(dp[low..high]) % MOD.
Time: O(high). Space: O(high).
What Trips People Up in Real Interviews
Worrying about duplicate strings when zero == one. Blocks of zeros and blocks of ones are different characters, so sequences never collide.
Generating actual strings with backtracking — exponential.
Summing only dp[high] instead of every length in [low, high].
Forgetting the modulo on the final sum.
Solution Code
def countGoodStrings(low, high, zero, one):
MOD = 10**9 + 7
dp = [0] * (high + 1)
dp[0] = 1
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
return sum(dp[low:high + 1]) % MODFrequently Asked Questions
What is the Count Ways To Build Good Strings problem?
Count Ways To Build Good Strings builds strings by repeatedly appending either `zero` copies of `0` or `one` copies of `1`, and asks how many distinct strings have length between `low` and `high`, modulo `10^9 + 7`. Only the length matters for counting, so it is Climbing Stairs with two custom step sizes.
How do you solve Count Ways To Build Good Strings?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Count Ways To Build Good Strings?
Count Ways To Build Good Strings is asked at Visa. It is a medium difficulty problem.
What are common mistakes on Count Ways To Build Good Strings?
- Worrying about duplicate strings when `zero == one`. Blocks of zeros and blocks of ones are different characters, so sequences never collide.
- Generating actual strings with backtracking — exponential.
- Summing only `dp[high]` instead of every length in `[low, high]`.
- Forgetting the modulo on the final sum.