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:

  1. We begin with an empty string.
  2. At each step, we can either add the character '0' exactly zero times or add the character '1' exactly one times to the string.
  3. 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 (returns 0).
  • If the length i is within the range [low, high], it is counted as a valid string and increments the ans by 1.
  • Then it calls itself twice recursively: once with the new length i + zero, and once with i + one, adding the results to the ans.
  • 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:

  1. Memoization Decorator (@cache): The function dfs is decorated with @cache, which is Python's built-in memoization decorator available from the functools module. This automatically remembers the results of the dfs function when it is called with specific arguments, so if the same length i 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.

  2. Recursive dfs Function: This is the function that will be doing the heavy lifting. It receives an integer i which represents the current length of the string being constructed.

    • When the function is called, it first checks if i exceeds high, in which case it returns 0 as this branch cannot produce any good strings.

    • If i is within the low to high range, the function increments ans by 1 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 and i + one, and adds their results to ans. These recursive calls will branch out and cover all possible string lengths that can be created from this point.

  3. Modulo Operation (% mod): The result of every increment and addition is taken modulo 10^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 modulo 10^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.

  4. Initialization and Result: The function dfs is initially called with 0 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 Evaluator

Example 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.

  1. We begin with an empty string s = "" and the current length i = 0.

  2. We call dfs(i) with i = 0. Since i is not greater than high, we do not return 0.

  3. Now, i is not within low and high, so we do not increment ans.

  4. We will call dfs(i + zero) which is dfs(1) and dfs(i + one) which is dfs(2).

  5. For dfs(1):

    • i = 1 is within the range [1, 2], so we increment ans by 1.
    • We make recursive calls dfs(1 + 1) and dfs(1 + 2) which are dfs(2) and dfs(3).
    • dfs(2) we already will calculate separately, so let's look at dfs(3):
      • i = 3 is greater than high, so this call returns 0 and does not contribute to ans.
  6. For dfs(2) (from the initial dfs(0) call):

    • i = 2 is within the range [1, 2], so we increment ans by 1.
    • We make recursive calls dfs(2 + 1) and dfs(2 + 2) which are dfs(3) and dfs(4).
    • Both dfs(3) and dfs(4) are greater than high and will return 0, contributing nothing to ans.
  7. At this point, we have ans = 1 for dfs(1) and ans = 1 for dfs(2). Our dfs(0) call will thus return ans = 1 + 1.

  8. The memoization ensures that during our recursive calls, the result of dfs(2) was calculated only once, saving computational time.

  9. With the modulo operation, the final result would simply be 2 % (10^9 + 7) = 2.

  10. Hence, the function countGoodStrings would return 2 as there are 2 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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

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

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More