Today I have done leetcode's May LeetCoding Challenge with cpp.

May LeetCoding Challenge 13

Description

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

const int MOD = 1e9 + 7;
class Solution {
public:
  int countGoodStrings(int low, int high, int zero, int one) {
    int dp[high + 1];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for(int i = min(zero, one); i <= high; ++i) {
      if(i >= zero) {
        dp[i] += dp[i - zero];
      }
      if(i >= one) {
        dp[i] += dp[i - one];
      }
      dp[i] %= MOD;
    }

    int answer = 0;
    for(int i = low; i <= high; ++i) {
      answer += dp[i];
      answer %= MOD;
    }

    return answer;
  }
};

// Accepted
// 36/36 cases passed (8 ms)
// Your runtime beats 94.56 % of cpp submissions
// Your memory usage beats 98.28 % of cpp submissions (6.5 MB)