2466. Count Ways To Build Good Strings

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

Solution 1: Memoization Search

C++

• class Solution {
  public:
      int countGoodStrings(int low, int high, int zero, int one) {
          const int mod = 1e9 + 7;
          vector<int> dp(high + 1, 0);
          dp[0] = 1; 
  
          for (int i = 1; i <= high; ++i) {
              if (i >= zero) dp[i] = (dp[i] + dp[i - zero]) % mod;
              if (i >= one) dp[i] = (dp[i] + dp[i - one]) % mod;
          }
  
          int result = 0;
          for (int i = low; i <= high; ++i) {
              result = (result + dp[i]) % mod;
          }
  
          return result;
      }
  };

JAVA

• class Solution {
      private static final int MOD = (int) 1e9 + 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];
      }
  }

PYTHON

• class Solution:
      def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
          mod = 10**9 + 7
          f = [-1] * (high + 1)
          
          def dfs(i):
              if i > high:
                  return 0
              if f[i] != -1:
                  return f[i]
              ans = 1 if low <= i <= high else 0
              ans += dfs(i + zero) + dfs(i + one)
              ans %= mod
              f[i] = ans
              return ans
          
          return dfs(0)