2466. Count Ways To Build Good Strings
Problem Description
In this problem, we are given four integers: zero
, one
, low
, and high
. Our goal is to count how many distinct strings can be constructed with the following rules:
- We begin with an empty string.
- At each step, we can either add the character '0' exactly
zero
times or add the character '1' exactlyone
times to the string. - This process can be repeated any number of times.
A "good" string is one that is built by these rules and has a length within the low
and high
range, inclusive. We are asked to return the number of distinct good strings that can be created subject to these rules. Because the answer could be very large, the final result should be returned modulo 10^9 + 7
.
Intuition
The intuition behind solving this problem lies in understanding that it is a question of combinatorial mathematics but modeled as a depth-first search (DFS) problem. Essentially, from any string of length i
, it can extend to a string of length i + zero
by appending zero
number of '0's or to a string of length i + one
by appending one
number of '1's.
The key point is to explore all the possible paths of constructing strings from length 0
to up to high
. However, if the length of a constructed string ever exceeds high
, it can no longer be part of a valid solution, so that branch is terminated.
To solve this efficiently, we use a recursive approach with memoization (caching results), which is implemented using the dfs
function in this case.
The dfs
function works as follows:
- It takes the current length
i
as the input. - It checks if the current length is greater than
high
, and if so, it ends the current branch (returns0
). - If the length
i
is within the range[low, high]
, it is counted as a valid string and increments theans
by1
. - Then it calls itself twice recursively: once with the new length
i + zero
, and once withi + one
, adding the results to theans
. - The answer is kept within the limit of modulo
10^9 + 7
and returned.
The final result starts with a call to dfs(0)
since we start with an empty string of length 0
. The function will then recursively compute the total number of distinct good strings. The use of the @cache
decorator implies that Python will automatically remember the results of the dfs
function calls with particular arguments, thus optimizing the number of computations by avoiding repeated calculation of the same function call.
Learn more about Dynamic Programming patterns.
Solution Approach
The solution for this problem utilizes a recursive depth-first search (DFS) approach with memoization. Here's a step-by-step implementation breakdown:
-
Memoization Decorator (
@cache
): The functiondfs
is decorated with@cache
, which is Python's built-in memoization decorator available from thefunctools
module. This automatically remembers the results of thedfs
function when it is called with specific arguments, so if the same lengthi
is encountered again, it will not recompute the results. This reduces the complexity significantly as repeated function calls with the same arguments use the cached results. -
Recursive
dfs
Function: This is the function that will be doing the heavy lifting. It receives an integeri
which represents the current length of the string being constructed.-
When the function is called, it first checks if
i
exceedshigh
, in which case it returns0
as this branch cannot produce any good strings. -
If
i
is within thelow
tohigh
range, the function incrementsans
by1
to account for the valid string of this particular length. -
The function then makes a recursive call to itself for the next possible lengths,
i + zero
andi + one
, and adds their results toans
. These recursive calls will branch out and cover all possible string lengths that can be created from this point.
-
-
Modulo Operation (
% mod
): The result of every increment and addition is taken modulo10^9 + 7
to ensure that the result never exceeds the specified limit. This is important because the number of strings can be quite large, and taking the result modulo10^9 + 7
keeps the numbers within integer limits. It's also a common requirement in programming problems to prevent integer overflow and to simplify large number arithmetic. -
Initialization and Result: The function
dfs
is initially called with0
as it starts with an empty string. The result of this call gives us the total count of valid "good" strings that can be constructed within the given parameters.
Here's the key part of the implementation that accomplishes this:
def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
@cache
def dfs(i):
if i > high:
return 0
ans = 0
if low <= i <= high:
ans += 1
ans += dfs(i + zero) + dfs(i + one)
return ans % mod
mod = 10**9 + 7
return dfs(0)
Through these steps, the algorithm efficiently enumerates and counts all possible "good" strings that can be formed based on the input parameters. The use of memoization in this context optimizes the recursive exploration, making this a practical approach for potentially large input values.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose we have the following inputs:
low = 1
high = 2
zero = 1
one = 2
We want to count distinct strings of '0's and '1's that can be constructed using zero
number of '0's and one
number of '1's, and the length of the string must be between low
and high
.
-
We begin with an empty string
s = ""
and the current lengthi = 0
. -
We call
dfs(i)
withi = 0
. Sincei
is not greater thanhigh
, we do not return0
. -
Now,
i
is not withinlow
andhigh
, so we do not incrementans
. -
We will call
dfs(i + zero)
which isdfs(1)
anddfs(i + one)
which isdfs(2)
. -
For
dfs(1)
:i = 1
is within the range[1, 2]
, so we incrementans
by1
.- We make recursive calls
dfs(1 + 1)
anddfs(1 + 2)
which aredfs(2)
anddfs(3)
. dfs(2)
we already will calculate separately, so let's look atdfs(3)
:i = 3
is greater thanhigh
, so this call returns0
and does not contribute toans
.
-
For
dfs(2)
(from the initialdfs(0)
call):i = 2
is within the range[1, 2]
, so we incrementans
by1
.- We make recursive calls
dfs(2 + 1)
anddfs(2 + 2)
which aredfs(3)
anddfs(4)
. - Both
dfs(3)
anddfs(4)
are greater thanhigh
and will return0
, contributing nothing toans
.
-
At this point, we have
ans = 1
fordfs(1)
andans = 1
fordfs(2)
. Ourdfs(0)
call will thus returnans = 1 + 1
. -
The memoization ensures that during our recursive calls, the result of
dfs(2)
was calculated only once, saving computational time. -
With the modulo operation, the final result would simply be
2 % (10^9 + 7) = 2
. -
Hence, the function countGoodStrings would return
2
as there are2
distinct strings ("01", "11") that can be constructed within the given parameters and rules.
Note that in the actual implementation, the function will not recompute dfs(2)
from both dfs(0)
and dfs(1)
due to the memoization decorator, as the result of dfs(2)
would have already been cached and retrieved from the memo on the second call.
Solution Implementation
1from functools import lru_cache # Import lru_cache for memoization
2
3class Solution:
4 def count_good_strings(self, low: int, high: int, zero: int, one: int) -> int:
5 # The mod value to ensure the results stay within the bounds of 10^9 + 7
6 mod = 10**9 + 7
7
8 # Use lru_cache to memoize results of recursive calls
9 @lru_cache(None)
10 def dfs(current_value):
11 """
12 Depth-first search to calculate number of good strings using recursion.
13
14 :param current_value: The current integer value being built
15 :return: The number of good strings from the current_value to high
16 """
17 # Base case: if current_value exceeds the 'high' value, no further strings can be considered
18 if current_value > high:
19 return 0
20
21 # Initialize answer for this state
22 ans = 0
23
24 # If the current value is within the range [low, high], count it as a good string
25 if low <= current_value <= high:
26 ans += 1
27
28 # Recursively count good strings adding zero and one to the current value
29 ans += dfs(current_value + zero)
30 ans += dfs(current_value + one)
31
32 # Return the total count modulo 10^9 + 7
33 return ans % mod
34
35 # Begin recursion with 0 as the starting value
36 return dfs(0)
37
38# Example usage:
39# If you have bounds and increment values, you can create an instance of Solution and call count_good_strings
40# sol = Solution()
41# result = sol.count_good_strings(low, high, zero, one)
42
1class Solution {
2 // Constant for the modulus to be used for result to prevent overflow
3 private static final int MOD = (int) 1e9 + 7;
4
5 // Cache for already computed results to avoid repeated calculations
6 private int[] memoization;
7
8 // Variables to store the lower and upper bounds of the string length
9 private int lowerBound;
10 private int upperBound;
11
12 // Variables to store the value to be added when encountering a '0' or '1' in the string
13 private int valueZero;
14 private int valueOne;
15
16 public int countGoodStrings(int low, int high, int zero, int one) {
17 // Initialize the cache array with a size of 'high + 1' and fill it with -1
18 // indicating that no calculations have been made for any index
19 memoization = new int[high + 1];
20 Arrays.fill(memoization, -1);
21
22 // Assign the provided bounds and values to the respective class fields
23 lowerBound = low;
24 upperBound = high;
25 valueZero = zero;
26 valueOne = one;
27
28 // Begin depth-first search from the starting point '0'
29 return dfs(0);
30 }
31
32 // Helper method that employs depth-first search to compute the good strings
33 private int dfs(int index) {
34 // If the current index is beyond the upper bound, return 0 as it cannot form a valid string
35 if (index > upperBound) {
36 return 0;
37 }
38 // If a result for the current index has already been computed (memoized), return it
39 if (memoization[index] != -1) {
40 return memoization[index];
41 }
42
43 // Initialize the answer for this index
44 long ans = 0;
45
46 // If the current index is within the bounds, count it as one valid string
47 if (index >= lowerBound && index <= upperBound) {
48 ans++;
49 }
50
51 // Use recurrence to count additional good strings by adding valueZero and valueOne to index recursively
52 ans += dfs(index + valueZero) + dfs(index + valueOne);
53
54 // Take modulus to prevent overflow
55 ans %= MOD;
56
57 // Cache the computed result for the current index before returning
58 memoization[index] = (int) ans;
59 return memoization[index];
60 }
61}
62
1class Solution {
2public:
3 // Declare the modulus as a constant expression since it does not change.
4 static constexpr int MOD = 1e9 + 7;
5
6 // Count the good strings with given constraints using memoization.
7 int CountGoodStrings(int low, int high, int zero, int one) {
8 // Use a vector for memoization, initialized with -1.
9 vector<int> memo(high + 1, -1);
10
11 // Define a lambda function for DFS (Depth-First Search) with memoization.
12 function<int(int)> DFS = [&](int i) -> int {
13 // Base case: if the current value is greater than 'high', no good strings can be formed.
14 if (i > high) return 0;
15
16 // If the current number of good strings has been calculated before, return the stored result.
17 if (memo[i] != -1) return memo[i];
18
19 // Initialize count starting with 1 if 'i' is within range [low, high].
20 long count = (i >= low && i <= high) ? 1 : 0;
21
22 // Recursively count the good strings by adding 'zero' and 'one' to the current value 'i'.
23 count += DFS(i + zero) + DFS(i + one);
24
25 // Ensure the count does not exceed the MOD.
26 count %= MOD;
27
28 // Store the result in the memoization vector and return it.
29 memo[i] = count;
30 return count;
31 };
32
33 // Start the DFS from 0.
34 return DFS(0);
35 }
36};
37
1// Define the modulus as a constant since it does not change.
2const MOD = 1e9 + 7;
3
4// Memoization table, using a Map to associate indices with their counts
5let memo: Map<number, number> = new Map();
6
7// Count the good strings with given constraints using memoization
8function countGoodStrings(low: number, high: number, zero: number, one: number): number {
9 // Clear the memoization table before a new computation
10 memo.clear();
11
12 // Helper function for DFS (Depth-First Search) with memoization
13 function dfs(current: number): number {
14 // Base case: if the current value is greater than 'high', no good strings can be formed
15 if (current > high) return 0;
16
17 // If the current number of good strings has been calculated before, return the stored result
18 if (memo.has(current)) return memo.get(current)!;
19
20 // Initialize count starting with 1 if 'current' is within the range [low, high]
21 let count: number = (current >= low && current <= high) ? 1 : 0;
22
23 // Recursively count the good strings by adding 'zero' and 'one' to the current value 'current'
24 count = (count + dfs(current + zero) + dfs(current + one)) % MOD;
25
26 // Store the result in the memoization table
27 memo.set(current, count);
28
29 return count;
30 }
31
32 // Start the DFS from 0 and return the total count
33 return dfs(0);
34}
35
Time and Space Complexity
The time complexity and space complexity analysis of the given code are as follows:
Time Complexity
The time complexity of the dfs
function primarily depends on the number of unique states it will visit during its execution. In this scenario, each state is represented by a value of i
that is checked against low
and high
. Since we increment i
by either zero
or one
, and we use memoization (@cache
), each state is computed only once.
The maximum number of unique states that can be visited can be roughly estimated as (high - low) / min(zero, one)
, because we're incrementally increasing i
starting from 0
to high
in steps of zero
or one
. However, we do perform extra checks when i
exceeds high
, so some overhead is present.
Therefore, the time complexity can be considered as O((high - low) / min(zero, one))
.
Space Complexity
The space complexity involves the stack space used by the recursive DFS calls and the space used by the memoization cache. Since we cache every unique state and each state calls dfs
twice (once with i + zero
and once with i + one
), the depth of the recursion tree can go up to high / min(zero, one)
in the worst case.
Therefore, the space complexity for the recursive stack is O(high / min(zero, one))
. Additionally, the cache will store each unique state, contributing a space complexity that is also in the order of O(high / min(zero, one))
.
Considering both the stack and the caching, the total space complexity can also be approximated as O(high / min(zero, one))
.
Learn more about how to find time and space complexity quickly using problem constraints.
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!