Watch 10 video solutions for Count Ways To Build Good Strings, a medium level problem involving Dynamic Programming. This walkthrough by NeetCodeIO has 10,932 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the integers zero, one, low, and high, we can construct a string by starting with an empty string, and then at each step perform either of the following:
'0' zero times.'1' one times.This can be performed any number of times.
A good string is a string constructed by the above process having a length between low and high (inclusive).
Return the number of different good strings that can be constructed satisfying these properties. Since the answer can be large, return it modulo 109 + 7.
Example 1:
Input: low = 3, high = 3, zero = 1, one = 1 Output: 8 Explanation: One possible valid good string is "011". It can be constructed as follows: "" -> "0" -> "01" -> "011". All binary strings from "000" to "111" are good strings in this example.
Example 2:
Input: low = 2, high = 3, zero = 1, one = 2 Output: 5 Explanation: The good strings are "00", "11", "000", "110", and "011".
Constraints:
1 <= low <= high <= 1051 <= zero, one <= lowProblem Overview: You build binary strings by repeatedly appending blocks of size zero or one. A string is considered good if its final length lies between low and high. The task is to count how many such strings can be constructed. Since the count grows quickly, results are returned modulo 1e9 + 7.
Approach 1: Backtracking (Exponential Time)
This approach explores every possible construction path using recursion. Starting from length 0, recursively append a block of size zero or one and continue building the string. Whenever the current length falls within [low, high], increment the count. Recursion stops when the length exceeds high. This brute-force strategy tries all combinations, which leads to roughly O(2^(high / min(zero, one))) time complexity with O(high) recursion depth space. It demonstrates the problem structure but becomes impractical for large high.
Approach 2: Recursion with Memoization (Top-Down DP)
The repeated subproblem is the number of ways to build a valid string starting from a given length. Cache results for each length so the recursion does not recompute the same states. For a state len, the transitions are len + zero and len + one. Each state is solved once and stored in a memo table. This reduces the time complexity to O(high) with O(high) space for the cache and recursion stack. This version clearly shows the overlapping subproblems typical of dynamic programming and is easier to derive from the brute force recursion.
Approach 3: Bottom-Up Dynamic Programming (Optimal)
Instead of recursion, build the solution iteratively. Let dp[i] represent the number of ways to build a string of length i. Initialize dp[0] = 1 since an empty string is the starting state. For each length i from 1 to high, compute dp[i] by adding contributions from dp[i - zero] and dp[i - one] if those indices are valid. While filling the array, accumulate the answer whenever i lies between low and high. This runs in O(high) time with O(high) space. The iterative DP avoids recursion overhead and is the most common implementation in interviews. It is a classic counting pattern in dynamic programming and closely related to state-transition problems seen with memoization and recursion.
Recommended for interviews: The bottom-up dynamic programming approach is the expected solution. Interviewers want to see recognition of overlapping subproblems and a clean dp[i] state transition. Showing the backtracking idea first demonstrates understanding of the search space, but converting it into an O(high) DP solution shows strong algorithmic thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking | Exponential | O(high) | Useful for understanding the brute-force search tree and generating all possible constructions. |
| Recursion + Memoization | O(high) | O(high) | Good when deriving the DP from recursion and eliminating repeated subproblems. |
| Bottom-Up Dynamic Programming | O(high) | O(high) | Preferred interview solution. Iterative, simple state transitions, and no recursion overhead. |