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 <= lowThe key observation in #2466 Count Ways To Build Good Strings is that a string can grow only by appending blocks of length zero or one. This naturally leads to a dynamic programming approach where we count the number of ways to build strings of each possible length.
Let dp[i] represent the number of ways to construct a string of length i. From any valid state, we can extend the string by adding either a block of size zero or one. Therefore, the transition depends on previously computed lengths such as i - zero and i - one. By iterating up to the maximum allowed length and maintaining results modulo 1e9+7, we can efficiently compute all possibilities.
Finally, sum the counts for lengths within the range [low, high] to obtain the answer. This bottom-up DP ensures each length is computed once, giving an efficient solution suitable for interview settings.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (Bottom-Up) | O(high) | O(high) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Calculate the number of good strings with length less or equal to some constant x.
Apply dynamic programming using the group size of consecutive zeros and ones.
We can solve this problem using a dynamic programming approach. The idea is to maintain a dp array where dp[i] represents the number of good strings of exact length i. Start with an empty string and attempt to form strings by appending '0's and '1's zero and one times respectively. For each length from low to high, we incrementally calculate the number of ways to achieve that length from smaller lengths and store them in dp[i].
Time Complexity: O(high)
Space Complexity: O(high)
1#include <iostream>
2#include <vector>
3#define MOD 1000000007
4
5using namespace std;
6
7int countGoodStrings(int low, int high, int zero, int one) {
8 vector<int> dp(high + 1, 0);
9 dp[0] = 1;
10 for (int i = 1; i <= high; i++) {
11 if (i - zero >= 0) dp[i] = (dp[i] + dp[i - zero]) % MOD;
12 if (i - one >= 0) dp[i] = (dp[i] + dp[i - one]) % MOD;
13 }
14 int result = 0;
for (int i = low; i <= high; i++) {
result = (result + dp[i]) % MOD;
}
return result;
}
int main() {
cout << countGoodStrings(3, 3, 1, 1) << endl;
return 0;
}In the C++ solution, we employ a dynamic programming array dp similar to the C solution, where dp[i] stores the number of ways to form a string of length i. We initialize dp[0] as 1, and iterate to fill other values based on prior calculations. Finally, the solution calculates the sum from dp[low] to dp[high] for the answer.
In this approach, we explore every possible string configuration using backtracking to find strings whose lengths fall between low and high. We use recursion to build strings by appending zero or one '0's and '1's, tracking lengths and adding valid ones to a result set. Although not as efficient as the DP method due to exponential complexity, it serves as an insightful means to intuitively grasp the construction of such strings.
Time Complexity: O(2^n) where n is high / min(zero, one)
Space Complexity: O(n) because of the recursion stack
1def countGoodStrings(low, high, zero, one):
2 MOD =
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, similar dynamic programming counting problems frequently appear in FAANG-style interviews. They test a candidate's ability to recognize state transitions, manage constraints, and implement efficient DP solutions.
A simple array or list is sufficient to store DP states for each string length. The array keeps track of the number of ways to reach each length, enabling constant-time transitions for dp[i - zero] and dp[i - one].
The optimal approach uses dynamic programming. Define dp[i] as the number of ways to build a string of length i, then transition using dp[i - zero] and dp[i - one]. After computing up to 'high', sum the counts between 'low' and 'high' while applying modulo 1e9+7.
Dynamic programming works well because the number of ways to form a string of length i depends on previously computed smaller lengths. This overlapping subproblem structure allows us to build results incrementally and avoid redundant calculations.
The backtracking solution in Python employs a recursive function to consider adding either zero or one characters to a string. It tracks the length of each created string and counts those which are valid. Once a length exceeds high, recursion stops further exploration from that branch.