2533. Number of Good Binary Strings
Problem Description
This problem presents a condition-based combinatorial challenge where we need to count the number of binary strings that adhere to specific grouping rules. The binary strings must:
- Have a length within the inclusive range specified by
minLength
andmaxLength
. - Contain blocks of consecutive
1
s where each block's size is a multiple of the givenoneGroup
. - Contain blocks of consecutive
0
s where each block's size is a multiple of the givenzeroGroup
.
Furthermore, we are asked to return the count of such "good" binary strings modulo 10^9 + 7
to handle large numbers that could result from the computation.
Intuition
Understanding the pattern of good binary strings can lead us to a dynamic programming approach. Given the conditions, we can incrementally build a binary string of length i
by adding a block of 1
s or 0
s at the end of a string, ensuring the following:
- Blocks must have sizes that are multiples of
oneGroup
orzeroGroup
. - We only add blocks if they produce strings within the desired length range.
The intuition behind the solution is to use a dynamic programming table to store the number of ways to form a good binary string of length i
, which we denote as f[i]
. Starting with the base case, f[0]
is set to 1, representing the empty string.
For each length i
, we look back oneGroup
and zeroGroup
lengths from i
and add up the ways because:
- If we are at length
i
and we add a block of1
s ofoneGroup
length, we can use all combinations of lengthi-oneGroup
to form new combinations. - Similarly, we can do the same with blocks of
0
s ofzeroGroup
length. - We take care to only add blocks if the resulting length does not exceed our maximum length constraint.
Finally, since we are only interested in strings with lengths between minLength
and maxLength
, we sum the values stored in our dynamic programming table from f[minLength]
to f[maxLength]
, ensuring we only count the strings of acceptable lengths.
Implementing this approach in a loop that iterates through the possible lengths of binary strings, we can compute the answer. It's important to take the modulo at each step to prevent integer overflow given the constraint on the output.
Learn more about Dynamic Programming patterns.
Solution Approach
The solution to the problem uses a dynamic programming approach, a common pattern in solving combinatorial problems where we build solutions to sub-problems and use those solutions to construct answers to larger problems. Here, the sub-problems involve finding the number of good binary strings of a smaller length, and these are combined to find the number of strings of larger lengths.
The implementation details are as follows:
-
Data Structure: We use a list
f
with lengthmaxLength + 1
. The indexi
in the list represents the number of good binary strings of lengthi
. It is initialized withf[0] = 1
(since the empty string is considered a good string) and0
for all other lengths. -
Algorithm: We iterate from
1
tomaxLength
to fill up the dynamic programming tablef
. For each lengthi
, we can either add a block of1
s or a block of0
s at the end of an existing good string which is shorter byoneGroup
orzeroGroup
respectively:-
If
i - oneGroup >= 0
, we can take all good strings of lengthi - oneGroup
and add a block of1
s to them. Thus, we updatef[i]
to include these new combinations by addingf[i - oneGroup]
. -
If
i - zeroGroup >= 0
, similarly, we can take all good strings of lengthi - zeroGroup
and add a block of0
s to them, updatingf[i]
to include these combinations by addingf[i - zeroGroup]
. -
We use the modulo operator at each update to ensure that we do not encounter integer overflow, since we are interested in the count modulo
10^9 + 7
.
-
-
Final Count: Once the dynamic programming table is complete, the last step is to obtain the sum of all
f[i]
values fori
betweenminLength
andmaxLength
inclusive, and take the modulo again to get the final count of good binary strings within the given length range.
Here is the core part of the solution, with comments added for clarification:
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
From the solution, we can see that the algorithm is a bottom-up dynamic programming solution since it builds up the answer iteratively. The space complexity of the algorithm is O(maxLength) because of the array f
, and the time complexity is O(maxLength) as well, because we iterate through the array once.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let us assume minLength
is 3, maxLength
is 5, oneGroup
is 2, and zeroGroup
is 3. We need to count the number of binary strings that fit the criteria based on the given conditions.
We initialize our dynamic programming array f
with the size of maxLength + 1
, which is f[0]
to f[5]
for this example. We start by setting f[0] = 1
since the empty string is a valid string and zero for all other lengths.
Now, we start populating f
from f[1]
to f[5]
:
-
For
i = 1
andi = 2
: We cannot add any blocks of1
s or0
s becauseoneGroup
andzeroGroup
are larger thani
. Thus,f[1]
andf[2]
remain 0. -
For
i = 3
: We can add a block of0
s becausei - zeroGroup = 0
andf[0] = 1
. Therefore,f[3]
becomes 1 after considering the block of0
s. We cannot add a block of1
s sinceoneGroup
is 2 and there's no way to form a1
block within this length. -
For
i = 4
: We can add a block of1
s sincei - oneGroup = 2
andf[2] = 0
. So,f[4]
becomes 0 + 0 = 0. We do not have a way to add consecutive0
s of lengthzeroGroup
to a string of length 2 (since that would exceed the current lengthi = 4
). -
For
i = 5
: We can add a block of1
s (f[3] = 1
from prior step), sof[5]
is updated to 1. We also check for zero blocks, but5 - zeroGroup
is less than0
and thus, cannot form a valid string.
To summarize the DP array: f[0] = 1
, f[1] = 0
, f[2] = 0
, f[3] = 1
, f[4] = 0
, f[5] = 1
.
Finally, to count the number of good strings of length between minLength
and maxLength
, we sum f[3]
, f[4]
, and f[5]
. The result is 1 + 0 + 1 = 2
. Thus, there are two "good" binary strings that satisfy the conditions between the length of 3 and 5, given the groupings of 1
s and 0
s.
The final answer is 2, and we will return this count modulo 10^9 + 7
, which in this simple case remains 2.
Solution Implementation
1class Solution:
2 def goodBinaryStrings(self, min_length: int, max_length: int, one_group: int, zero_group: int) -> int:
3 MOD = 10**9 + 7 # define the modulo value
4
5 # Initialize the dynamic programming table `f` with the base case f[0] = 1 and the rest 0s
6 f = [1] + [0] * max_length
7
8 # Calculate the number of good binary strings for each length up to maxLength
9 for i in range(1, len(f)):
10 # If adding a group of 1s is possible, update f[i]
11 if i - one_group >= 0:
12 f[i] += f[i - one_group]
13
14 # If adding a group of 0s is possible, update f[i]
15 if i - zero_group >= 0:
16 f[i] += f[i - zero_group]
17
18 # Modulo operation to keep the number within the bounds of MOD
19 f[i] %= MOD
20
21 # Sum up all combinations from minLength to maxLength, and take modulo
22 return sum(f[min_length:]) % MOD
23
1class Solution {
2 public int goodBinaryStrings(int minLength, int maxLength, int oneGroup, int zeroGroup) {
3 // Define the modulo constant as it is frequently used in the computation
4 final int MODULO = (int) 1e9 + 7;
5
6 // Initialize an array to store the number of good binary strings of length i
7 int[] goodStringsCount = new int[maxLength + 1];
8 // A binary string of length 0 is considered a good string (base case)
9 goodStringsCount[0] = 1;
10
11 // Start to fill the array with the number of good binary strings for each length
12 for (int i = 1; i <= maxLength; ++i) {
13 // If it's possible to have a group of 1's,
14 // add the count of the previous length where a 1's group can be appended
15 if (i - oneGroup >= 0) {
16 goodStringsCount[i] = (goodStringsCount[i] + goodStringsCount[i - oneGroup]) % MODULO;
17 }
18 // Similarly, if it's possible to have a group of 0's,
19 // add the count of the previous length where a 0's group can be appended
20 if (i - zeroGroup >= 0) {
21 goodStringsCount[i] = (goodStringsCount[i] + goodStringsCount[i - zeroGroup]) % MODULO;
22 }
23 }
24
25 // Initialize the variable that will store the sum of all good strings
26 // within the given range
27 int sumGoodStrings = 0;
28
29 // Accumulate the good strings count within the specified length range
30 for (int i = minLength; i <= maxLength; ++i) {
31 sumGoodStrings = (sumGoodStrings + goodStringsCount[i]) % MODULO;
32 }
33
34 // Return the total number of good binary strings
35 return sumGoodStrings;
36 }
37}
38
1class Solution {
2public:
3 int goodBinaryStrings(int min_length, int max_length, int one_group, int zero_group) {
4 const int MOD = 1e9 + 7; // Modulus value for avoiding integer overflow.
5 int dp[max_length + 1]; // An array to store the dynamic programming state.
6 memset(dp, 0, sizeof dp); // Initialize the dynamic programming array with zeros.
7 dp[0] = 1; // The base case: there's one way to form an empty string.
8
9 // Calculate the number of good binary strings of each length
10 for (int i = 1; i <= max_length; ++i) {
11 if (i - one_group >= 0) {
12 dp[i] = (dp[i] + dp[i - one_group]) % MOD; // Add valid strings ending in a '1' group.
13 }
14 if (i - zero_group >= 0) {
15 dp[i] = (dp[i] + dp[i - zero_group]) % MOD; // Add valid strings ending in a '0' group.
16 }
17 }
18
19 // Sum up the counts of good strings for all lengths within the given range
20 int answer = 0;
21 for (int i = min_length; i <= max_length; ++i) {
22 answer = (answer + dp[i]) % MOD; // Aggregate the results using modular addition.
23 }
24
25 return answer; // Return the total count of good binary strings of valid lengths.
26 }
27};
28
1function goodBinaryStrings(
2 minLength: number,
3 maxLength: number,
4 oneGroup: number,
5 zeroGroup: number,
6): number {
7 // Modular constant to prevent overflows in calculations
8 const MOD: number = 10 ** 9 + 7;
9
10 // Initialize an array to hold counts for each length up to maxLength
11 const goodStringCounts: number[] = Array(maxLength + 1).fill(0);
12
13 // Base case: An empty string is considered a good string
14 goodStringCounts[0] = 1;
15
16 // Generate counts for good strings of each length up to maxLength
17 for (let currentLength = 1; currentLength <= maxLength; ++currentLength) {
18 // If the current length is at least as large as the minimum
19 // required '1's group, we can add previous count;
20 // this implies addition of a '1's group
21 if (currentLength >= oneGroup) {
22 goodStringCounts[currentLength] += goodStringCounts[currentLength - oneGroup];
23 }
24
25 // If the current length is at least as large as the minimum
26 // required '0's group, we can add previous count;
27 // this implies addition of a '0's group
28 if (currentLength >= zeroGroup) {
29 goodStringCounts[currentLength] += goodStringCounts[currentLength - zeroGroup];
30 }
31
32 // Apply modulus operation to prevent integer overflow
33 goodStringCounts[currentLength] %= MOD;
34 }
35
36 // Sum all counts from minLength to maxLength (inclusive) to find
37 // the total number of good strings within the given range.
38 // The result is returned with a modulus operation to keep it within the int bounds.
39 return goodStringCounts.slice(minLength).reduce((accumulator, currentCount) => accumulator + currentCount, 0) % MOD;
40}
41
Time and Space Complexity
The given Python code defines a method within the Solution
class that calculates the number of good binary strings with certain properties. The method goodBinaryStrings
counts the number of binary strings with a specified minimum and maximum length, where each group of consecutive 1
's is at least oneGroup
in length and each group of consecutive 0
's is at least zeroGroup
in length.
Time Complexity
To analyze the time complexity of the method goodBinaryStrings
, consider the following points:
- The list
f
is initialized to have a length ofmaxLength + 1
. - There is a single loop that iterates
maxLength
times. - Within the loop, there are two constant-time conditional checks and arithmetic operations.
- The final summation using
sum(f[minLength:])
runs inO(n)
time wheren
ismaxLength - minLength + 1
.
Combining these factors, the overall time complexity is as follows:
- Initialization of
f
:O(maxLength)
- Loop operations:
O(maxLength)
- Final summation:
O(maxLength - minLength)
Since maxLength
dominates the runtime as it tends to be larger than maxLength - minLength
, the total time complexity is O(maxLength)
.
Space Complexity
For the space complexity of the method goodBinaryStrings
, consider the following points:
- A list
f
is used to store intermediate results and has a size ofmaxLength + 1
.
Therefore, the space complexity is O(maxLength)
, as this is the most significant factor in determining the amount of space used by the algorithm.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the relationship between a tree and a graph?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!