Scale Engineer

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 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 <= 105
  • 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:

  1. Appending zero '0's to a valid string of length length - zero.
  2. 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.

class Solution {    int MOD = 1_000_000_007;    int[] memo;     public int countGoodStrings(int low, int high, int zero, int one) {        memo = new int[high + 1];        java.util.Arrays.fill(memo, -1);                int totalWays = 0;        for (int length = low; length <= high; length++) {            totalWays = (totalWays + solve(length, zero, one)) % MOD;        }        return totalWays;    }     private int solve(int length, int zero, int one) {        if (length == 0) {            return 1; // Base case: one way to form an empty string        }        if (length < 0) {            return 0; // Impossible to form a string of negative length        }        if (memo[length] != -1) {            return memo[length]; // Return cached result        }         // Recurrence relation        int ways = (solve(length - zero, zero, one) + solve(length - one, zero, one)) % MOD;                memo[length] = ways; // Cache the result        return ways;    }}

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

Solutions

class Solution {private  static final int MOD = (int)1 e9 + 7;private  int[] f;private  int lo;private  int hi;private  int zero;private  int one;public  int countGoodStrings(int low, int high, int zero, int one) {    f = new int[high + 1];    Arrays.fill(f, -1);    lo = low;    hi = high;    this.zero = zero;    this.one = one;    return dfs(0);  }private  int dfs(int i) {    if (i > hi) {      return 0;    }    if (f[i] != -1) {      return f[i];    }    long ans = 0;    if (i >= lo && i <= hi) {      ++ans;    }    ans += dfs(i + zero) + dfs(i + one);    ans %= MOD;    f[i] = (int)ans;    return f[i];  }}

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 →

Next problem