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:

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

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:

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:

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:

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

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: