2533. Number of Good Binary Strings

You are given four integers minLenght, maxLength, oneGroup and zeroGroup.

A binary string is good if it satisfies the following conditions:

• The length of the string is in the range [minLength, maxLength].
• The size of each block of consecutive 1’s is a multiple of oneGroup.

• For example in a binary string 00110111100 sizes of each block of consecutive ones are [2,4].

• The size of each block of consecutive 0’s is a multiple of zeroGroup.

• For example, in a binary string 00110111100 sizes of each block of consecutive ones are [2,1,2].

Return the number of good binary strings. Since the answer may be too large, return it modulo 109 + 7.

Note that 0 is considered a multiple of all the numbers.

class Solution {
public:
    int goodBinaryStrings(int minLength, int maxLength, int oneGroup, int zeroGroup) {
        long long res = 0, mod = 1e9 + 7;
        vector<long long> dp1(maxLength + 1), dp2(maxLength + 1);
        dp1[oneGroup] = dp2[zeroGroup] = 1;
        for(int i = 1; i <= maxLength; i++) {
            int l1 = i - oneGroup, l2 = i - zeroGroup;
            if(l1 >= 0) dp1[i] = (dp1[i] + dp1[l1] + dp2[l1]) % mod;
            if(l2 >= 0) dp2[i] = (dp2[i] + dp1[l2] + dp2[l2]) % mod;
            if(i >= minLength) res = (res + dp1[i] + dp2[i]) % mod;
        }
        return res;
    }
};