2533. Number of Good Binary Strings π
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 ofoneGroup
.- For example in a binary string
00110111100
sizes of each block of consecutive ones are[2,4]
.
- For example in a binary string
- The size of each block of consecutive
0
's is a multiple ofzeroGroup
.- For example, in a binary string
00110111100
sizes of each block of consecutive zeros are[2,1,2]
.
- For example, in a binary string
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 \geq 1 \end{cases} $$
The final answer is $f[minLength] + f[minLength + 1] + \cdots + f[maxLength]$.
The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n=maxLength$.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|