Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2466.html

2466. Count Ways To Build Good Strings

• Difficulty: Medium.
• Related Topics: Dynamic Programming.
• Similar Questions: Climbing Stairs.

Problem

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 (Java, C++, Python)

• Java
• C++
• Python
• Go

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

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).

All Problems

All Solutions