LeetCode 2533 - Number of Good Binary Strings

The problem asks us to count how many binary strings satisfy a very specific structural rule. We are given four integers: - minLength, the minimum allowed length of a valid string - maxLength, the maximum allowed length of a valid string - oneGroup, the required divisibility…

leetcodemediumdynamic-programming

LeetCode Problem 2533

Difficulty: 🟡 Medium
Topics: Dynamic Programming

Solution

Problem Understanding

The problem asks us to count how many binary strings satisfy a very specific structural rule.

We are given four integers:

  • minLength, the minimum allowed length of a valid string
  • maxLength, the maximum allowed length of a valid string
  • oneGroup, the required divisibility condition for every consecutive block of 1s
  • zeroGroup, the required divisibility condition for every consecutive block of 0s

A binary string is considered good if every contiguous block of identical characters has a length divisible by the corresponding group size.

For example, suppose:

  • oneGroup = 2
  • zeroGroup = 3

Then every consecutive run of 1s must have length 2, 4, 6, and so on, while every consecutive run of 0s must have length 3, 6, 9, and so on.

The important detail is that blocks are independent. A string may alternate between zeros and ones any number of times, as long as every block individually satisfies its divisibility rule.

We need to count all good binary strings whose total length lies within the inclusive range [minLength, maxLength].

The answer can become extremely large, so we must return it modulo:

$$10^9 + 7$$

The constraints are critical:

  • maxLength can be as large as 100000
  • Any algorithm exponential in the string length is impossible
  • Even quadratic solutions are too slow in practice

This immediately suggests that we need a linear or near-linear dynamic programming solution.

Several edge cases are important:

  • When oneGroup = 1, any run of ones is allowed
  • When zeroGroup = 1, any run of zeros is allowed
  • When minLength = maxLength, we only count strings of one exact size
  • Some lengths may be impossible to construct at all
  • Very large ranges require careful modulo handling and efficient memory usage

Another subtle observation is that the problem is fundamentally about constructing strings by appending valid blocks. That insight leads directly to the optimal dynamic programming formulation.

Approaches

Brute Force Approach

A straightforward approach would generate every binary string whose length lies between minLength and maxLength.

For each generated string, we would scan through it and compute the lengths of every consecutive block of zeros and ones. We would then verify whether:

  • every zero block length is divisible by zeroGroup
  • every one block length is divisible by oneGroup

If both conditions hold, we increment the answer.

This approach is correct because it explicitly checks every possible candidate string.

However, it is completely impractical for the given constraints. A binary string of length n has:

$$2^n$$

possible configurations.

Since maxLength can be 100000, exhaustive generation is impossible.

Key Insight

Instead of thinking about individual characters, we should think about building strings block by block.

A valid string can always be formed by repeatedly appending:

  • a block of 0s whose size is exactly zeroGroup
  • a block of 1s whose size is exactly oneGroup

Why is this enough?

Because any valid block length is a multiple of the group size. A block of length 6 with zeroGroup = 3 can be viewed as two appended valid zero blocks of length 3.

This transforms the problem into a counting problem over string lengths.

Suppose:

  • dp[length] represents the number of good strings of total length length

Then:

  • if we append a valid zero block of size zeroGroup, we transition from length - zeroGroup
  • if we append a valid one block of size oneGroup, we transition from length - oneGroup

This gives the recurrence:

$$dp[i] = dp[i - zeroGroup] + dp[i - oneGroup]$$

whenever those indices are valid.

This dynamic programming solution runs in linear time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force $O(2^{maxLength} \cdot maxLength)$ $O(maxLength)$ Generates every binary string and validates each
Optimal Dynamic Programming $O(maxLength)$ $O(maxLength)$ Counts valid constructions by length

Algorithm Walkthrough

  1. Create a dynamic programming array dp of size maxLength + 1.

The value dp[i] will store the number of good binary strings with total length exactly i. 2. Initialize the base case:

dp[0] = 1

This represents the empty string.

The empty string is important because it acts as the starting point for constructing larger strings. 3. Iterate through all lengths from 1 to maxLength.

For each length i, compute how many valid strings can end at this length. 4. Check whether we can append a zero block.

If:

i >= zeroGroup

then any valid string of length:

i - zeroGroup

can become a valid string of length i by appending a block of 0s of size zeroGroup.

So:

dp[i] += dp[i - zeroGroup]
  1. Check whether we can append a one block.

If:

i >= oneGroup

then any valid string of length:

i - oneGroup

can become a valid string of length i by appending a block of 1s of size oneGroup.

So:

dp[i] += dp[i - oneGroup]
  1. Apply modulo after every update.

Since the number of valid strings grows rapidly, we compute:

dp[i] %= MOD
  1. Whenever the current length lies inside the required range:
minLength <= i <= maxLength

add dp[i] to the final answer. 8. Return the accumulated answer modulo $10^9 + 7$.

Why it works

The recurrence works because every good string must end with either:

  • a valid block of zeros
  • a valid block of ones

Removing that final block leaves another smaller good string.

Conversely, every smaller good string can generate a larger good string by appending a valid block.

This creates a complete and non-overlapping decomposition of all good strings, which guarantees that the dynamic programming recurrence counts every valid string exactly once.

Python Solution

class Solution:
    def goodBinaryStrings(
        self,
        minLength: int,
        maxLength: int,
        oneGroup: int,
        zeroGroup: int
    ) -> int:
        MOD = 10**9 + 7

        dp = [0] * (maxLength + 1)
        dp[0] = 1

        answer = 0

        for length in range(1, maxLength + 1):
            if length >= zeroGroup:
                dp[length] += dp[length - zeroGroup]

            if length >= oneGroup:
                dp[length] += dp[length - oneGroup]

            dp[length] %= MOD

            if minLength <= length <= maxLength:
                answer = (answer + dp[length]) % MOD

        return answer

The implementation follows the exact recurrence described in the algorithm section.

The dp array stores the number of valid strings for each exact length. We begin with dp[0] = 1 because there is exactly one way to construct a string of length zero, namely the empty string.

For every length from 1 to maxLength, we attempt two transitions:

  • append a valid zero block
  • append a valid one block

If either transition is possible, we add the number of ways to reach the previous length.

The modulo operation is applied after each iteration to prevent integer overflow and keep values bounded.

Finally, whenever the current length falls inside the required range, we add its count into the running answer.

Go Solution

func goodBinaryStrings(minLength int, maxLength int, oneGroup int, zeroGroup int) int {
	const MOD int = 1_000_000_007

	dp := make([]int, maxLength+1)
	dp[0] = 1

	answer := 0

	for length := 1; length <= maxLength; length++ {
		if length >= zeroGroup {
			dp[length] += dp[length-zeroGroup]
		}

		if length >= oneGroup {
			dp[length] += dp[length-oneGroup]
		}

		dp[length] %= MOD

		if length >= minLength {
			answer = (answer + dp[length]) % MOD
		}
	}

	return answer
}

The Go implementation mirrors the Python solution closely.

The primary difference is explicit integer handling. Since Go uses fixed-width integer types, we consistently apply modulo arithmetic to prevent overflow.

Slices are used instead of Python lists, but the indexing logic remains identical.

The algorithm still runs in linear time and uses linear auxiliary space.

Worked Examples

Example 1

Input:
minLength = 2
maxLength = 3
oneGroup = 1
zeroGroup = 2

We construct the dp array step by step.

Initial state:

Length dp
0 1

Length = 1

We cannot append a zero block because 1 < 2.

We can append a one block because 1 >= 1.

$$dp[1] = dp[0] = 1$$

Length dp
0 1
1 1

Current valid lengths counted:

none, since 1 < minLength

Length = 2

Append zero block:

$$dp[2] += dp[0] = 1$$

Append one block:

$$dp[2] += dp[1] = 1$$

So:

$$dp[2] = 2$$

The valid strings are:

  • "00"
  • "11"
Length dp
0 1
1 1
2 2

Answer so far:

$$2$$

Length = 3

Append zero block:

$$dp[3] += dp[1] = 1$$

Append one block:

$$dp[3] += dp[2] = 2$$

So:

$$dp[3] = 3$$

The valid strings are:

  • "001"
  • "100"
  • "111"

Final answer:

$$2 + 3 = 5$$

Example 2

Input:
minLength = 4
maxLength = 4
oneGroup = 4
zeroGroup = 3

Initial state:

Length dp
0 1

Length = 1

No valid transition.

$$dp[1] = 0$$

Length = 2

No valid transition.

$$dp[2] = 0$$

Length = 3

Can append a zero block:

$$dp[3] = dp[0] = 1$$

This corresponds to:

000

But length 3 is outside the required range.

Length = 4

Can append a one block:

$$dp[4] = dp[0] = 1$$

This corresponds to:

1111

Final answer:

$$1$$

Complexity Analysis

Measure Complexity Explanation
Time $O(maxLength)$ We process each length exactly once
Space $O(maxLength)$ The DP array stores one value per length

The algorithm performs a constant amount of work for every integer from 1 through maxLength.

No nested loops or recursive branching exist, so the total runtime is linear.

The memory usage is also linear because we maintain one dynamic programming value for every possible length.

Test Cases

sol = Solution()

# Provided examples
assert sol.goodBinaryStrings(2, 3, 1, 2) == 5  # example 1
assert sol.goodBinaryStrings(4, 4, 4, 3) == 1  # example 2

# Minimum possible input
assert sol.goodBinaryStrings(1, 1, 1, 1) == 2  # "0", "1"

# Only one valid length
assert sol.goodBinaryStrings(2, 2, 2, 2) == 2  # "00", "11"

# No constructions for some lengths
assert sol.goodBinaryStrings(1, 1, 2, 2) == 0  # impossible length

# oneGroup = 1 allows arbitrary one-block sizes
assert sol.goodBinaryStrings(3, 3, 1, 3) == 4

# zeroGroup = 1 allows arbitrary zero-block sizes
assert sol.goodBinaryStrings(3, 3, 2, 1) == 4

# Larger range
assert sol.goodBinaryStrings(1, 5, 1, 1) == 62  # all binary strings except empty

# Exact large block
assert sol.goodBinaryStrings(5, 5, 5, 5) == 2  # "00000", "11111"

# Impossible exact length
assert sol.goodBinaryStrings(7, 7, 4, 6) == 0

# Stress-style test
result = sol.goodBinaryStrings(1, 100000, 1, 1)
assert isinstance(result, int)  # verifies large input handling

Test Summary

Test Why
(2,3,1,2) Validates the first official example
(4,4,4,3) Validates the second official example
(1,1,1,1) Smallest possible valid input
(2,2,2,2) Exact block-sized construction
(1,1,2,2) Impossible target length
(3,3,1,3) Arbitrary one-block sizes
(3,3,2,1) Arbitrary zero-block sizes
(1,5,1,1) Every binary string becomes valid
(5,5,5,5) Single exact block constructions
(7,7,4,6) No valid decomposition exists
Large stress test Confirms scalability

Edge Cases

One important edge case occurs when both oneGroup and zeroGroup equal 1. In this scenario, every possible binary string is valid because every positive integer is divisible by 1. A buggy implementation might still accidentally restrict transitions or mis-handle counting. The dynamic programming recurrence handles this naturally because every length can transition from the previous length using either a zero block or a one block.

Another critical edge case occurs when certain lengths cannot be constructed at all. For example:

minLength = 1
maxLength = 1
oneGroup = 2
zeroGroup = 2

No valid string of length 1 exists because all valid blocks must have even size. The implementation correctly leaves dp[1] = 0 because neither transition condition is satisfied.

A third important edge case involves very large inputs near the upper constraint limit of 100000. Recursive solutions or brute-force enumeration would fail due to exponential growth or stack overflow. The iterative bottom-up dynamic programming solution avoids recursion entirely and processes each length exactly once, ensuring efficient performance even at maximum scale.

A fourth subtle edge case involves exact-length queries where minLength == maxLength. Some implementations mistakenly accumulate all lengths up to maxLength. This solution only adds counts when the current length lies within the required interval, so exact-length queries work correctly without special handling.