LeetCode 696: Count Binary Substrings

Problem Restatement

We are given a binary string s.

We need to count non-empty substrings that satisfy both rules:

Rule	Meaning
Equal counts	The substring has the same number of 0s and 1s
Grouped characters	All 0s are consecutive and all 1s are consecutive

Substrings that appear multiple times are counted multiple times. For example, "00110011" has two separate occurrences of "0011" and two separate occurrences of "01", and each occurrence counts.

Input and Output

Item	Meaning
Input	A binary string s
Output	Number of valid substrings
Characters	Only '0' and '1'
Constraint	1 <= s.length <= 10^5

Example function shape:

def countBinarySubstrings(s: str) -> int:
    ...

Examples

Example 1:

s = "00110011"

Valid substrings are:

"0011"
"01"
"1100"
"10"
"0011"
"01"

Answer:

6

The full string "00110011" is not valid because the 0s and 1s are split into multiple groups.

Example 2:

s = "10101"

Valid substrings are:

"10"
"01"
"10"
"01"

Answer:

4

First Thought: Check Every Substring

A direct solution is to generate every substring and test whether:

1. it has the same number of 0s and 1s,
2. it has only one group of 0s and one group of 1s.

This works logically, but there are O(n^2) substrings.

Checking each substring also costs time, so this approach is too slow for large input.

Key Insight

A valid substring must cross exactly one boundary between two groups.

For example:

000111

has two groups:

Group	Length
000	3
111	3

Valid substrings around this boundary are:

01
0011
000111

There are 3 of them.

Now consider:

00011

The group lengths are 3 and 2.

Valid substrings are:

01
0011

There are:

min(3, 2) = 2

So every adjacent pair of groups contributes:

min(previous_group_length, current_group_length)

valid substrings.

Algorithm

Track two group lengths while scanning:

Variable	Meaning
prev	Length of the previous consecutive character group
curr	Length of the current consecutive character group

Initialize:

prev = 0
curr = 1
answer = 0

Then scan from index 1 to the end.

If the current character equals the previous character:

curr += 1

we are still inside the same group.

Otherwise, the group changed.

At that boundary:

answer += min(prev, curr)
prev = curr
curr = 1

After the loop, add the contribution from the final adjacent group pair:

answer += min(prev, curr)

Return answer.

Walkthrough

Consider:

s = "00110011"

The groups are:

00 | 11 | 00 | 11

Group lengths:

[2, 2, 2, 2]

Adjacent group contributions:

Adjacent groups	Contribution
00, 11	min(2, 2) = 2
11, 00	min(2, 2) = 2
00, 11	min(2, 2) = 2

Total:

2 + 2 + 2 = 6

Answer:

6

Now consider:

s = "10101"

The groups are:

1 | 0 | 1 | 0 | 1

Group lengths:

[1, 1, 1, 1, 1]

There are four adjacent group pairs, each contributing 1.

Answer:

4

Correctness

Every valid substring contains exactly two consecutive groups: one group of 0s and one group of 1s.

It cannot contain more than two groups, because then either the 0s or the 1s would be split apart and would not be grouped consecutively.

For any two adjacent groups with lengths a and b, a valid substring can use x characters from the end of the first group and x characters from the start of the second group.

The value of x can be any integer from 1 through min(a, b).

So this adjacent pair contributes exactly min(a, b) valid substrings.

The algorithm scans the string and computes each group length. At every group boundary, it adds the contribution from the previous adjacent pair. After the scan, it adds the last pair.

Therefore, every valid substring is counted once, and no invalid substring is counted.

Complexity

Let n = len(s).

Metric	Value	Why
Time	O(n)	We scan the string once
Space	O(1)	Only counters are stored

Implementation

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        answer = 0
        prev = 0
        curr = 1

        for i in range(1, len(s)):
            if s[i] == s[i - 1]:
                curr += 1
            else:
                answer += min(prev, curr)
                prev = curr
                curr = 1

        answer += min(prev, curr)

        return answer

Code Explanation

We use:

prev = 0
curr = 1

At the start, there is no previous group yet, and the current group contains the first character.

When adjacent characters are equal:

if s[i] == s[i - 1]:
    curr += 1

we extend the current group.

When the character changes:

answer += min(prev, curr)

we finish one adjacent group pair and add its contribution.

Then the old current group becomes the previous group:

prev = curr

and the new current group starts with length 1:

curr = 1

After the loop, the final pair has not been added yet, so we add it:

answer += min(prev, curr)

Testing

def run_tests():
    s = Solution()

    assert s.countBinarySubstrings("00110011") == 6
    assert s.countBinarySubstrings("10101") == 4

    assert s.countBinarySubstrings("0") == 0
    assert s.countBinarySubstrings("01") == 1
    assert s.countBinarySubstrings("00110") == 3
    assert s.countBinarySubstrings("000111") == 3
    assert s.countBinarySubstrings("00011") == 2
    assert s.countBinarySubstrings("111000111") == 6

    print("all tests passed")

run_tests()

Test meaning:

Test	Expected	Why
"00110011"	6	Official example
"10101"	4	Official example
"0"	0	No opposite bit group
"01"	1	One valid substring
"00110"	3	Contributions 2 + 1
"000111"	3	Three balanced substrings
"00011"	2	Limited by smaller group
"111000111"	6	Two boundaries, each contributes 3