Count Ways To Build Good Strings

Leetcode Problem:

• Count Ways To Build Good Strings

Summary

• Find the number of different good strings that can be constructed satisfying the given properties.

Approach

• This problem can be solved using dynamic programming
• We use a memoization table to store the results of subproblems and avoid redundant computation.

Complexity

• O(n * zero * one), where n is the range of possible lengths (high - low + 1)

Explanation

• The `getCnt` function calculates the number of good strings of a given length that can be constructed using the given number of zeros and ones
• It uses memoization to store the results of subproblems and avoid redundant computation
• The `countGoodStrings` function iterates over the range of possible lengths and calls `getCnt` to calculate the total number of good strings
• The result is then taken modulo 10^9 + 7 to avoid overflow.

Solution Code:

#define MOD 1000000007
class Solution {
public:
    int memo[100001];
    long long getCnt(int length, int zero, int one){
        if(length < 0) return 0;
        if(length == 0){
            return 1;
        }
        if(memo[length] != -1) return memo[length];
        long long ret = 0;
        ret += getCnt(length - zero, zero, one);
        ret %= MOD;
        ret += getCnt(length - one , zero, one);
        ret %= MOD;
        return memo[length] = ret;
    }
    int countGoodStrings(int low, int high, int zero, int one) {
        memset(memo, -1, sizeof(memo));
        long long ans = 0;
        for(int i = low; i <= high; i++){
            ans += getCnt(i, zero, one);
            ans %= MOD;
        }
        return ans;
    }
};