Count Ways To Build Good Strings — Problem & Solution
Count Ways To Build Good Strings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Ways To Build Good Strings is a medium coding problem on dynamic programming, asked in Amazon, Google and Salesforce interviews.
- Difficulty: Medium
- Topics: Dynamic Programming
- Asked at: Amazon, Google, Salesforce
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Build a binary string starting from the empty string. At each step you may append zero copies of '0' or one copies of '1'.
A string is good when its length is between low and high inclusive. Return the number of different good strings you can build, modulo 10^9 + 7.
Example 1
Input: low = 3, high = 3, zero = 1, one = 1
Output: 8
Explanation: Every binary string of length 3.
Example 2
Input: low = 2, high = 3, zero = 1, one = 2
Output: 5
Explanation: Length 2 gives "00" and "11"; length 3 gives "000", "011" and "110".
Example 3
Input: low = 1, high = 1, zero = 1, one = 1
Output: 2
Constraints
1 <= low <= high <= 1000001 <= zero, one <= high
Hints for Count Ways To Build Good Strings
Hint 1
Only the current length matters — the actual characters never constrain the next step.
Hint 2
dp[i]is the number of ways to build a string of length exactlyi.Hint 3
dp[i] = dp[i - zero] + dp[i - one], and the answer sumsdp[i]overlow ≤ i ≤ high.
How to solve Count Ways To Build Good Strings
The state collapses to the length. A string of length i is built by appending a block of zero zeros to a string of length i - zero, or a block of one ones to one of length i - one — and those two cases are disjoint because the final block differs.
Approach
- Set
dp[0] = 1for the empty string. - For
ifrom 1 tohigh, adddp[i - zero]anddp[i - one]where the indices are valid. - Sum
dp[i]foriin[low, high], all modulo10^9 + 7.
Why it works
Every non-empty buildable string ends in exactly one kind of block, so classifying by that block partitions the ways — no double counting and nothing missed. Different build sequences also give different strings, because the blocks are read off the string's own structure from the right.
Complexity
- Time —
O(high) - Space —
O(high)
Pitfalls
- The two cases are added, not multiplied — they are alternatives.
- Reducing modulo only at the end overflows; reduce at every addition.
zeroandonemay be equal, in which casedp[i]doubles each valid step.
Reference solution
Python
def countGoodStrings(low: int, high: int, zero: int, one: int) -> int:
MOD = 1000000007
dp = [0] * (high + 1)
dp[0] = 1
ans = 0
for i in range(1, high + 1):
if i >= zero:
dp[i] = (dp[i] + dp[i - zero]) % MOD
if i >= one:
dp[i] = (dp[i] + dp[i - one]) % MOD
if i >= low:
ans = (ans + dp[i]) % MOD
return ansJava
public static int countGoodStrings(int low, int high, int zero, int one) {
final int MOD = 1000000007;
int[] dp = new int[high + 1];
dp[0] = 1;
int ans = 0;
for (int i = 1; i <= high; i++) {
if (i >= zero) dp[i] = (dp[i] + dp[i - zero]) % MOD;
if (i >= one) dp[i] = (dp[i] + dp[i - one]) % MOD;
if (i >= low) ans = (ans + dp[i]) % MOD;
}
return ans;
}C++
int countGoodStrings(int low, int high, int zero, int one) {
const int MOD = 1000000007;
vector<int> dp(high + 1, 0);
dp[0] = 1;
int ans = 0;
for (int i = 1; i <= high; i++) {
if (i >= zero) dp[i] = (dp[i] + dp[i - zero]) % MOD;
if (i >= one) dp[i] = (dp[i] + dp[i - one]) % MOD;
if (i >= low) ans = (ans + dp[i]) % MOD;
}
return ans;
}JavaScript
var countGoodStrings = function(low, high, zero, one) {
var MOD = 1000000007;
var dp = [];
for (var t = 0; t <= high; t++) dp.push(0);
dp[0] = 1;
var ans = 0;
for (var i = 1; i <= high; i++) {
if (i >= zero) dp[i] = (dp[i] + dp[i - zero]) % MOD;
if (i >= one) dp[i] = (dp[i] + dp[i - one]) % MOD;
if (i >= low) ans = (ans + dp[i]) % MOD;
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming