Is Number of Good Binary Strings easy or hard?

The problem is rated Medium because recognizing the dynamic programming state is the main challenge. Once you identify that each string length depends on previous lengths, the implementation becomes straightforward.

Number of Good Binary Strings Python/Java solution

Most solutions implement a DP array and iterate from 1 to high while updating counts modulo 1e9+7. The same logic works across Python, Java, C++, Go, and TypeScript because it relies on simple array operations and modular arithmetic.

How to solve Number of Good Binary Strings in O(n)?

Treat the string length as the DP state. Initialize dp[0] = 1, then iterate from 1 to high and update dp[i] using dp[i - zero] and dp[i - one] if those indices are valid. Accumulate the answer for all i between low and high. This processes each length once, giving O(high) time complexity.

What is the best approach for Number of Good Binary Strings?

The most practical approach uses bottom-up dynamic programming. Define dp[i] as the number of ways to build a binary string of length i. For each length, add contributions from dp[i - zero] and dp[i - one]. This computes all states in O(high) time and O(high) space.

Is Number of Good Binary Strings asked at Google/Amazon/Meta?

Dynamic programming counting problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. Variants involving string construction, step transitions, or path counting are common interview patterns.

What data structure is used in Number of Good Binary Strings?

The core data structure is a one-dimensional dynamic programming array. Each index represents the number of ways to build a string of a specific length, and transitions reference earlier indices.

What is the time complexity of Number of Good Binary Strings?

The optimal dynamic programming solution runs in O(high) time because each length from 1 to high is processed once. Each state performs constant-time transitions from earlier states. Space complexity is also O(high) for storing the DP array.

Description Hints 2 Solution Video 15:46

2533. Number of Good Binary Strings

Medium52.8% acceptance1 companyPremium elsewhere, free here

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 10⁹ + 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 <= 10⁵
1 <= oneGroup, zeroGroup <= maxLength

Asked at 1 company

Expedia

Topics

Dynamic Programming

Hints open one at a time

Hint 1

If we maintain DP(i, x) where i denotes the length and x denotes the last written integer (0 or 1), then it is not hard to solve in O(maxLength * max(zeroGroup, oneGroup)).

Hint 2

Notice that from DP(i, 0) we only have a transition to DP(j, 1) where (j - i) mod oneGroup == 0 and j > i. Similarly with DP(i,1). So we can use prefix sum to optimize our DP and solve it in O(maxLength).

15:46

Still stuck?Read the written solution, or watch a walkthrough.

Open solution