Skip to main content
Talentd

Number of Good Binary Strings - Solution & Explanation

MediumPremiumFree on FleetCodeDynamic Programming7 min readAsked at: Expedia
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You need to count how many binary strings have a length between low and high. The string can only be built by repeatedly appending a block of zero zeros or a block of one ones. The result can grow very large, so return the count modulo 1e9 + 7.

Approach 1: Recursion with Memoization (Top-Down DP) (Time: O(high), Space: O(high))

Think of the problem as building the string length step by step. From a current length len, you can move to len + zero or len + one. A recursive function explores these possibilities until the length exceeds high. Memoization stores the result for each length so repeated states are not recomputed. The key insight is that the number of valid strings depends only on the current length, not on the actual characters used. This turns the recursion tree into a linear number of states.

Approach 2: Bottom-Up Dynamic Programming (Time: O(high), Space: O(high))

Create a DP array where dp[i] represents the number of ways to build a string of length i. Initialize dp[0] = 1 since there is one way to build an empty string. Iterate from length 1 to high, and update dp[i] using previous states: add dp[i - zero] if i >= zero and add dp[i - one] if i >= one. Whenever i falls between low and high, include dp[i] in the final answer. This approach avoids recursion and directly builds the solution using dynamic programming.

Approach 3: Space-Optimized DP Counting (Time: O(high), Space: O(high))

The transition only depends on earlier lengths, so the DP can be computed sequentially without storing additional structures. Maintain a single array up to high and accumulate results during iteration. The algorithm still uses the same recurrence but focuses on minimizing overhead and improving clarity. The logic resembles counting paths in a graph where nodes represent lengths and edges represent valid extensions.

Recommended for interviews: The bottom-up DP solution is what interviewers expect. It clearly shows that you recognized the recurrence relation and implemented an efficient state transition. Explaining the recursive formulation first demonstrates understanding of the state space, while converting it to an iterative dynamic programming solution shows practical problem-solving skill. Problems like this often appear alongside other state-transition questions involving memoization and counting paths.

Solution

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursion with MemoizationO(high)O(high)Useful for reasoning about the state transitions and converting a recursive idea into DP
Bottom-Up Dynamic ProgrammingO(high)O(high)Best general solution for interviews and competitive programming
Space-Optimized DP CountingO(high)O(high)When implementing a clean iterative solution with minimal overhead

Video Solution

Number of Good Binary Strings - LeetCode Premium • LeetCode Україна • 501 views views

Watch 1 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Number of Good Binary Strings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Special Binary String