Question

2466. Count Ways To Build Good Strings

中文文档

Description

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

Solutions

Solution 1: Memoization Search

We design a function $dfs(i)$ to represent the number of good strings constructed starting from the $i$-th position. The answer is $dfs(0)$.

The computation process of the function $dfs(i)$ is as follows:

• If $i > high$, return $0$;
• If $low \leq i \leq high$, increment the answer by $1$, then after $i$, we can add either zero number of $0$s or one number of $1$s. Therefore, the answer is incremented by $dfs(i + zero) + dfs(i + one)$.

During the process, we need to take the modulus of the answer, and we can use memoization search to reduce redundant computations.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n = high$.

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

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];
  }
}

class Solution {
public:
  const int mod = 1e9 + 7;

  int countGoodStrings(int low, int high, int zero, int one) {
    vector<int> f(high + 1, -1);
    function<int(int)> dfs = [&](int i) -> int {
      if (i > high) return 0;
      if (f[i] != -1) return f[i];
      long ans = i >= low && i <= high;
      ans += dfs(i + zero) + dfs(i + one);
      ans %= mod;
      f[i] = ans;
      return ans;
    };
    return dfs(0);
  }
};

func countGoodStrings(low int, high int, zero int, one int) int {
  f := make([]int, high+1)
  for i := range f {
    f[i] = -1
  }
  const mod int = 1e9 + 7
  var dfs func(i int) int
  dfs = func(i int) int {
    if i > high {
      return 0
    }
    if f[i] != -1 {
      return f[i]
    }
    ans := 0
    if i >= low && i <= high {
      ans++
    }
    ans += dfs(i+zero) + dfs(i+one)
    ans %= mod
    f[i] = ans
    return ans
  }
  return dfs(0)
}