LeetCode 2533. Number of Good Binary Strings Solution in Java, C++, Python & More | Explanation + Code

Description

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 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 zeros 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.

 

Example 1:

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:

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 <= 105
• 1 <= oneGroup, zeroGroup <= maxLength

Solutions

Solution 1: Dynamic Programming

We define f[i] as the number of strings of length i that meet the condition. The state transition equation is:

f[i] = \begin{cases} 1 & i = 0 \ f[i - oneGroup] + f[i - zeroGroup] & i ≥ 1 \end{cases}

The final answer is f[minLength] + f[minLength + 1] + … + f[maxLength].

The time complexity is O(n), and the space complexity is O(n), where n=maxLength.

PythonJavaC++GoTypeScript

class Solution: def goodBinaryStrings( self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int ) -> int: mod = 10**9 + 7 f = [1] + [0] * maxLength for i in range(1, len(f)): if i - oneGroup >= 0: f[i] += f[i - oneGroup] if i - zeroGroup >= 0: f[i] += f[i - zeroGroup] f[i] %= mod return sum(f[minLength:]) % mod(code-box)

class Solution { public int goodBinaryStrings(int minLength, int maxLength, int oneGroup, int zeroGroup) { final int mod = (int) 1e9 + 7; int[] f = new int[maxLength + 1]; f[0] = 1; for (int i = 1; i <= maxLength; ++i) { if (i - oneGroup >= 0) { f[i] = (f[i] + f[i - oneGroup]) % mod; } if (i - zeroGroup >= 0) { f[i] = (f[i] + f[i - zeroGroup]) % mod; } } int ans = 0; for (int i = minLength; i <= maxLength; ++i) { ans = (ans + f[i]) % mod; } return ans; } }(code-box)

class Solution { public: int goodBinaryStrings(int minLength, int maxLength, int oneGroup, int zeroGroup) { const int mod = 1e9 + 7; int f[maxLength + 1]; memset(f, 0, sizeof f); f[0] = 1; for (int i = 1; i <= maxLength; ++i) { if (i - oneGroup >= 0) { f[i] = (f[i] + f[i - oneGroup]) % mod; } if (i - zeroGroup >= 0) { f[i] = (f[i] + f[i - zeroGroup]) % mod; } } int ans = 0; for (int i = minLength; i <= maxLength; ++i) { ans = (ans + f[i]) % mod; } return ans; } };(code-box)

func goodBinaryStrings(minLength int, maxLength int, oneGroup int, zeroGroup int) (ans int) { const mod int = 1e9 + 7 f := make([]int, maxLength+1) f[0] = 1 for i := 1; i <= maxLength; i++ { if i-oneGroup >= 0 { f[i] += f[i-oneGroup] } if i-zeroGroup >= 0 { f[i] += f[i-zeroGroup] } f[i] %= mod } for _, v := range f[minLength:] { ans = (ans + v) % mod } return }(code-box)

function goodBinaryStrings( minLength: number, maxLength: number, oneGroup: number, zeroGroup: number, ): number { const mod = 10 ** 9 + 7; const f: number[] = Array(maxLength + 1).fill(0); f[0] = 1; for (let i = 1; i <= maxLength; ++i) { if (i >= oneGroup) { f[i] += f[i - oneGroup]; } if (i >= zeroGroup) { f[i] += f[i - zeroGroup]; } f[i] %= mod; } return f.slice(minLength).reduce((a, b) => a + b, 0) % mod; }(code-box)