Problem

You are given four integers minLength, 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 00 _11_ 0 _1111_ 00 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 _00_ 11 _0_ 1111 _00_ sizes of each block of consecutive zeros are [2,1,2].

Return the number ofgood 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.

Examples

Example 1:

1
2
3
4

Input: minLength = 2, maxLength = 3, oneGroup = 1, zeroGroup = 2
Output: 5
Explanation: There are 5 good binary strings in this example: "00", "11", "001", "100", and "111".
It can be proven that there are only 5 good strings satisfying all conditions.

Example 2:

1
2
3
4

Input: minLength = 4, maxLength = 4, oneGroup = 4, zeroGroup = 3
Output: 1
Explanation: There is only 1 good binary string in this example: "1111".
It can be proven that there is only 1 good string satisfying all conditions.

Constraints:

  • 1 <= minLength <= maxLength <= 10^5
  • 1 <= oneGroup, zeroGroup <= maxLength

Solution

Method 1 – DP with Group Constraints

Intuition

We build good binary strings by appending blocks of 1’s (length multiple of oneGroup) and blocks of 0’s (length multiple of zeroGroup). Use DP: dp[i] = number of good strings of length i ending with either 0 or 1 block.

Approach

  1. dp[i] = number of good strings of length i.
  2. For each i, add dp[i-zeroGroup] (if i >= zeroGroup) and dp[i-oneGroup] (if i >= oneGroup).
  3. Initialize dp[0] = 1 (empty string is valid for block size 0).
  4. Sum dp[i] for i in [minLength, maxLength].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <vector>
using namespace std;
class Solution {
public:
    int goodBinaryStrings(int minLength, int maxLength, int oneGroup, int zeroGroup) {
        const int MOD = 1e9+7;
        vector<int> dp(maxLength+1, 0);
        dp[0] = 1;
        for (int i = 1; i <= maxLength; ++i) {
            if (i >= oneGroup) dp[i] = (dp[i] + dp[i-oneGroup]) % MOD;
            if (i >= zeroGroup) dp[i] = (dp[i] + dp[i-zeroGroup]) % MOD;
        }
        int ans = 0;
        for (int i = minLength; i <= maxLength; ++i) ans = (ans + dp[i]) % MOD;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func goodBinaryStrings(minLength, maxLength, oneGroup, zeroGroup int) int {
    mod := int(1e9+7)
    dp := make([]int, maxLength+1)
    dp[0] = 1
    for i := 1; i <= maxLength; i++ {
        if i >= oneGroup { dp[i] = (dp[i] + dp[i-oneGroup]) % mod }
        if i >= zeroGroup { dp[i] = (dp[i] + dp[i-zeroGroup]) % mod }
    }
    ans := 0
    for i := minLength; i <= maxLength; i++ { ans = (ans + dp[i]) % mod }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int goodBinaryStrings(int minLength, int maxLength, int oneGroup, int zeroGroup) {
        int MOD = (int)1e9+7;
        int[] dp = new int[maxLength+1];
        dp[0] = 1;
        for (int i = 1; i <= maxLength; ++i) {
            if (i >= oneGroup) dp[i] = (dp[i] + dp[i-oneGroup]) % MOD;
            if (i >= zeroGroup) dp[i] = (dp[i] + dp[i-zeroGroup]) % MOD;
        }
        int ans = 0;
        for (int i = minLength; i <= maxLength; ++i) ans = (ans + dp[i]) % MOD;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun goodBinaryStrings(minLength: Int, maxLength: Int, oneGroup: Int, zeroGroup: Int): Int {
        val MOD = 1_000_000_007
        val dp = IntArray(maxLength+1)
        dp[0] = 1
        for (i in 1..maxLength) {
            if (i >= oneGroup) dp[i] = (dp[i] + dp[i-oneGroup]) % MOD
            if (i >= zeroGroup) dp[i] = (dp[i] + dp[i-zeroGroup]) % MOD
        }
        var ans = 0
        for (i in minLength..maxLength) ans = (ans + dp[i]) % MOD
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:
        MOD = 10**9+7
        dp = [0]*(maxLength+1)
        dp[0] = 1
        for i in range(1, maxLength+1):
            if i >= oneGroup:
                dp[i] = (dp[i] + dp[i-oneGroup]) % MOD
            if i >= zeroGroup:
                dp[i] = (dp[i] + dp[i-zeroGroup]) % MOD
        return sum(dp[minLength:maxLength+1]) % MOD
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn good_binary_strings(min_length: i32, max_length: i32, one_group: i32, zero_group: i32) -> i32 {
        let min_length = min_length as usize;
        let max_length = max_length as usize;
        let one_group = one_group as usize;
        let zero_group = zero_group as usize;
        let m = 1_000_000_007;
        let mut dp = vec![0; max_length+1];
        dp[0] = 1;
        for i in 1..=max_length {
            if i >= one_group { dp[i] = (dp[i] + dp[i-one_group]) % m; }
            if i >= zero_group { dp[i] = (dp[i] + dp[i-zero_group]) % m; }
        }
        let mut ans = 0;
        for i in min_length..=max_length { ans = (ans + dp[i]) % m; }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    goodBinaryStrings(minLength: number, maxLength: number, oneGroup: number, zeroGroup: number): number {
        const MOD = 1e9+7;
        const dp = Array(maxLength+1).fill(0);
        dp[0] = 1;
        for (let i = 1; i <= maxLength; ++i) {
            if (i >= oneGroup) dp[i] = (dp[i] + dp[i-oneGroup]) % MOD;
            if (i >= zeroGroup) dp[i] = (dp[i] + dp[i-zeroGroup]) % MOD;
        }
        let ans = 0;
        for (let i = minLength; i <= maxLength; ++i) ans = (ans + dp[i]) % MOD;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(N), where N = maxLength.
  • 🧺 Space complexity: O(N).