2466. Count Ways To Build Good Strings LeetCode Solution

In this guide, you will get 2466. Count Ways To Build Good Strings LeetCode Solution with the best time and space complexity. The solution to Count Ways To Build Good Strings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Ways To Build Good Strings solution in C++
Count Ways To Build Good Strings solution in Java
Count Ways To Build Good Strings solution in Python
Additional Resources

2466. Count Ways To Build Good Strings LeetCode Solution image

Problem Statement of 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

Complexity Analysis

Time Complexity: O(\texttt{high})
Space Complexity: O(\texttt{high})

2466. Count Ways To Build Good Strings LeetCode Solution in C++

class Solution {
 public:
  int countGoodStrings(int low, int high, int zero, int one) {
    constexpr int kMod = 1'000'000'007;
    int ans = 0;
    // dp[i] := the number of good strings with length i
    vector<int> dp(high + 1);
    dp[0] = 1;

    for (int i = 1; i <= high; ++i) {
      if (i >= zero)
        dp[i] = (dp[i] + dp[i - zero]) % kMod;
      if (i >= one)
        dp[i] = (dp[i] + dp[i - one]) % kMod;
      if (i >= low)
        ans = (ans + dp[i]) % kMod;
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

2466. Count Ways To Build Good Strings LeetCode Solution in Java

class Solution {
  public int countGoodStrings(int low, int high, int zero, int one) {
    final int kMod = 1_000_000_007;
    int ans = 0;
    // dp[i] := the number of good strings with length i
    int[] dp = new int[high + 1];
    dp[0] = 1;

    for (int i = 1; i <= high; ++i) {
      if (i >= zero)
        dp[i] = (dp[i] + dp[i - zero]) % kMod;
      if (i >= one)
        dp[i] = (dp[i] + dp[i - one]) % kMod;
      if (i >= low)
        ans = (ans + dp[i]) % kMod;
    }

    return ans;
  }
}
// code provided by PROGIEZ

2466. Count Ways To Build Good Strings LeetCode Solution in Python

class Solution:
  def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
    kMod = 1_000_000_007
    ans = 0
    # dp[i] := the number of good strings with length i
    dp = [1] + [0] * high

    for i in range(1, high + 1):
      if i >= zero:
        dp[i] = (dp[i] + dp[i - zero]) % kMod
      if i >= one:
        dp[i] = (dp[i] + dp[i - one]) % kMod
      if i >= low:
        ans = (ans + dp[i]) % kMod

    return ans
 # code by PROGIEZ