2466. Count Ways To Build Good Strings
Asked at Visa
Difficulty
Medium
Time
O(high)
Space
O(high)
Pattern
Dynamic Programming
Companies
1
Problem
You build a binary string step by step, starting from an empty string. At each step you do exactly one of two things: append a block of zero copies of '0', or append a block of one copies of '1'. You may repeat this as many times as you like, including zero times.
A string is called good if it can be built this way and its final length is between low and high, inclusive. Return how many different good strings exist. Two strings count as different if their characters differ at any position, so the order of the blocks matters.
Because the count can be huge, return it modulo 10^9 + 7. Note that only the total length decides whether a string is good — the actual arrangement of characters is fixed by the sequence of block choices you made.
Building a string block by block
Constraints
- ●
1 <= low <= high <= 10^5 - ●
1 <= zero, one <= low
Examples
low = 3, high = 3, zero = 1, one = 18low = 2, high = 3, zero = 1, one = 25Asked At
1 companies| 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).
dp counts strings by length
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
O(high) timedef 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 runs in O(high) time and O(high) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.