Count Ways To Build Good Strings

Med

#2250Time: O(high) - Each state `solve(i)` for `i` from 0 to `high` is computed only once due to memoization. The main loop runs `high - low + 1` times, and each call to `solve` will trigger computations that fill the memo table up to `high` in total.Space: O(high) - This is for the memoization array of size `high + 1` and the depth of the recursion stack, which can also go up to `high` in the worst case.1 company

Patterns

Dynamic Programming

Companies

Citadel

Prompt

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:

Append the character '0' zero times.
Append the character '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 10⁹ + 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 <= 10⁵
1 <= zero, one <= low

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses recursion to solve the problem by breaking it down into smaller, overlapping subproblems. To avoid the exponential time complexity of naive recursion, we use a memoization table (an array) to store the results of subproblems once they are computed. The number of ways to form a string of a certain length is the sum of the ways to form the strings from which it could have been created in the last step.

Algorithm

1. Define a constant MOD = 10^9 + 7.
1. Create a memoization array memo of size high + 1 and initialize it with a sentinel value (e.g., -1) to indicate that a state has not been computed.
1. Define a recursive helper function, let's call it solve(length), that computes the number of ways to build a string of the given length.
1. Inside solve(length):
- If length == 0, return 1 (base case for the empty string).
- If length < 0, return 0 (impossible to form).
- If memo[length] is not the sentinel value, it means we have already computed this subproblem, so return memo[length].
- Otherwise, recursively calculate the result using the recurrence: ways = (solve(length - zero) + solve(length - one)) % MOD.
- Store the computed result in memo[length] before returning it to avoid re-computation.
1. In the main function, initialize a variable totalWays = 0.
1. Iterate from length = low to high. In each iteration, call solve(length) and add the result to totalWays, taking the modulo to keep the sum within the integer limits.
1. Return totalWays.

Walkthrough

The problem has optimal substructure and overlapping subproblems, making it a perfect candidate for dynamic programming. We can define a function, count(length), which calculates the number of ways to construct a string of a given length.

A string of length can be formed by either:

Appending zero '0's to a valid string of length length - zero.
Appending one '1's to a valid string of length length - one.

This gives us the recurrence relation: count(length) = count(length - zero) + count(length - one). The base case is count(0) = 1, representing the single empty string. If length < 0, the number of ways is 0.

A naive recursive implementation would be very slow. We optimize this by using a memoization array, memo, to cache the result for each length. The main logic then involves calling this memoized recursive function for each length from low to high and summing up the results, taking the modulo at each step.

1class Solution {2    int MOD = 1_000_000_007;3    int[] memo;4 5    public int countGoodStrings(int low, int high, int zero, int one) {6        memo = new int[high + 1];7        java.util.Arrays.fill(memo, -1);8        9        int totalWays = 0;10        for (int length = low; length <= high; length++) {11            totalWays = (totalWays + solve(length, zero, one)) % MOD;12        }13        return totalWays;14    }15 16    private int solve(int length, int zero, int one) {17        if (length == 0) {18            return 1; // Base case: one way to form an empty string19        }20        if (length < 0) {21            return 0; // Impossible to form a string of negative length22        }23        if (memo[length] != -1) {24            return memo[length]; // Return cached result25        }26 27        // Recurrence relation28        int ways = (solve(length - zero, zero, one) + solve(length - one, zero, one)) % MOD;29        30        memo[length] = ways; // Cache the result31        return ways;32    }33}

Complexity

Time

O(high) - Each state `solve(i)` for `i` from 0 to `high` is computed only once due to memoization. The main loop runs `high - low + 1` times, and each call to `solve` will trigger computations that fill the memo table up to `high` in total.

Space

O(high) - This is for the memoization array of size `high + 1` and the depth of the recursion stack, which can also go up to `high` in the worst case.

Trade-offs

Pros

It's a direct translation of the recurrence relation, which can be more intuitive to formulate.
It only computes the states that are actually needed to reach the target lengths.

Cons

Can have higher constant overhead due to recursive function calls compared to an iterative solution.
In some languages or environments with strict recursion depth limits, it could theoretically lead to a stack overflow error for very large inputs, though this is not an issue for the given constraints (high <= 10^5).

This is an iterative approach that builds the solution from the ground up, which is often more efficient than its recursive counterpart. We use a DP array to store the number of ways to form strings of each possible length, starting from length 0 and iterating up to high. This avoids recursion and its associated overhead.

Algorithm

1. Define a constant MOD = 10^9 + 7.
1. Create a DP array dp of size high + 1 to store the number of ways to form a string for each length.
1. Initialize the base case: dp[0] = 1, as there is one way to form an empty string (by doing nothing).
1. Iterate with a loop variable i from 1 to high.
1. Inside the loop, calculate dp[i] using the recurrence relation:
- ways = 0
- If i >= zero, it means we can form a string of length i by appending zero '0's to any string of length i - zero. So, add dp[i - zero] to ways.
- If i >= one, similarly, add dp[i - one] to ways.
- Set dp[i] = ways % MOD.
1. After populating the dp array, initialize a variable result = 0 to store the final count of good strings.
1. Iterate from i = low to high, and for each i, add dp[i] to result, taking the modulo at each addition.
1. Return result.

Walkthrough

We can solve this problem iteratively using a dynamic programming array, let's call it dp, of size high + 1. The value dp[i] will store the number of ways to construct a string of length exactly i.

The base case is dp[0] = 1, representing the single empty string which has a length of 0.

We then iterate from i = 1 up to high. To calculate dp[i], we consider the two ways a string of length i could have been formed in the final step:

By appending zero '0's to a string of length i - zero. The number of ways to do this is dp[i - zero]. This is only possible if i >= zero.
By appending one '1's to a string of length i - one. The number of ways to do this is dp[i - one]. This is only possible if i >= one.

Thus, the state transition is dp[i] = (dp[i - zero] + dp[i - one]) % MOD. After filling the dp array, the total number of 'good' strings is simply the sum of dp[i] for all i in the range [low, high].

1class Solution {2    public int countGoodStrings(int low, int high, int zero, int one) {3        int MOD = 1_000_000_007;4        int[] dp = new int[high + 1];5        dp[0] = 1; // Base case: one way to form an empty string6 7        for (int i = 1; i <= high; i++) {8            // Number of ways to form a string of length i9            if (i >= zero) {10                dp[i] = (dp[i] + dp[i - zero]) % MOD;11            }12            if (i >= one) {13                dp[i] = (dp[i] + dp[i - one]) % MOD;14            }15        }16 17        int result = 0;18        for (int i = low; i <= high; i++) {19            result = (result + dp[i]) % MOD;20        }21 22        return result;23    }24}

Complexity

Time

O(high) - The first loop runs `high` times to populate the DP table. The second loop runs `high - low + 1` times. The total time complexity is dominated by the first loop, making it proportional to `high`.

Space

O(high) - We use an array of size `high + 1` to store the DP states.

Trade-offs

Pros

Generally more efficient in practice than the top-down approach due to the lack of recursive call overhead.
Guaranteed not to cause a stack overflow.
The iterative logic is often considered cleaner and easier to reason about for tabulation-style DP.

Cons

It computes the number of ways for all lengths up to high, even if some are not strictly necessary (e.g., if low is large). However, these smaller lengths are required to compute the larger ones, so this is not a significant drawback.

Solutions

Solution

1class Solution {2private3  static final int MOD = (int)1 e9 + 7;4private5  int[] f;6private7  int lo;8private9  int hi;10private11  int zero;12private13  int one;14public15  int countGoodStrings(int low, int high, int zero, int one) {16    f = new int[high + 1];17    Arrays.fill(f, -1);18    lo = low;19    hi = high;20    this.zero = zero;21    this.one = one;22    return dfs(0);23  }24private25  int dfs(int i) {26    if (i > hi) {27      return 0;28    }29    if (f[i] != -1) {30      return f[i];31    }32    long ans = 0;33    if (i >= lo && i <= hi) {34      ++ans;35    }36    ans += dfs(i + zero) + dfs(i + one);37    ans %= MOD;38    f[i] = (int)ans;39    return f[i];40  }41}

1class Solution {2public:3  const int mod = 1e9 + 7;4  int countGoodStrings(int low, int high, int zero, int one) {5    vector<int> f(high + 1, -1);6    function<int(int)> dfs = [&](int i) -> int {7      if (i > high)8        return 0;9      if (f[i] != -1)10        return f[i];11      long ans = i >= low && i <= high;12      ans += dfs(i + zero) + dfs(i + one);13      ans %= mod;14      f[i] = ans;15      return ans;16    };17    return dfs(0);18  }19};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem