Welcome to Subscribe On Youtube

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

Solution 2: Dynamic programming

This implementation uses dynamic programming. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.

• Java
• C++
• Python
• Go
• TypeScript
• Javascript

• 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);
      }
  };
  

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

• 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)
  }
  

• // Solution 2
  function countGoodStrings(low: number, high: number, zero: number, one: number): number {
      const mod = 10 ** 9 + 7;
      const f: number[] = new Array(high + 1).fill(0);
      f[0] = 1;
  
      for (let i = 1; i <= high; i++) {
          if (i >= zero) f[i] += f[i - zero];
          if (i >= one) f[i] += f[i - one];
          f[i] %= mod;
      }
  
      const ans = f.slice(low, high + 1).reduce((acc, cur) => acc + cur, 0);
  
      return ans % mod;
  }
  
  

• // Solution 2
  /**
   * @param {number} low
   * @param {number} high
   * @param {number} zero
   * @param {number} one
   * @return {number}
   */
  function countGoodStrings(low, high, zero, one) {
      const mod = 10 ** 9 + 7;
      const f = Array(high + 1).fill(0);
      f[0] = 1;
  
      for (let i = 1; i <= high; i++) {
          if (i >= zero) f[i] += f[i - zero];
          if (i >= one) f[i] += f[i - one];
          f[i] %= mod;
      }
  
      const ans = f.slice(low, high + 1).reduce((acc, cur) => acc + cur, 0);
  
      return ans % mod;
  }
  
  

All Problems

All Solutions