LeetCode 696 - Count Binary Substrings

The problem gives us a binary string, meaning the string contains only the characters '0' and '1'. We need to count how many substrings satisfy two conditions simultaneously: 1. The substring contains the same number of 0s and 1s. 2.

leetcodeeasytwo-pointersstring

LeetCode Problem 696

Difficulty: 🟢 Easy
Topics: Two Pointers, String

Solution

Problem Understanding

The problem gives us a binary string, meaning the string contains only the characters '0' and '1'. We need to count how many substrings satisfy two conditions simultaneously:

  1. The substring contains the same number of 0s and 1s.
  2. All 0s are grouped together and all 1s are grouped together.

The second condition is extremely important. It means the substring must look like one consecutive block of 0s followed by one consecutive block of 1s, or one consecutive block of 1s followed by one consecutive block of 0s.

Valid examples include:

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

Invalid examples include:

  • "001100" because there are multiple transitions between 0 and 1
  • "0101" because the characters are not grouped consecutively

The input size can be as large as 10^5, which immediately tells us that an O(n^2) or O(n^3) solution will likely be too slow. We need an efficient linear-time solution.

A key observation is that valid substrings always span exactly two consecutive groups of characters. For example:

00110011

can be grouped as:

00 | 11 | 00 | 11

If two adjacent groups have lengths a and b, then they contribute:

min(a, b)

valid substrings.

For example:

00 and 11

have lengths 2 and 2, so they contribute:

  • "01"
  • "0011"

which is min(2, 2) = 2.

Important edge cases include very short strings, strings with only one repeated character, and strings where groups have dramatically different sizes.

For example:

  • "0" produces 0
  • "11111" produces 0
  • "0001111" produces 3

The problem guarantees that the string is non-empty and contains only valid binary characters.

Approaches

Brute Force Approach

A brute-force solution would generate every possible substring and check whether it satisfies the required conditions.

For each substring, we would need to verify:

  • The number of 0s equals the number of 1s
  • All 0s appear consecutively
  • All 1s appear consecutively

There are O(n^2) substrings, and validating each substring can take O(n) time in the worst case. This leads to an O(n^3) solution.

Even with optimizations, a brute-force approach remains too slow for n = 10^5.

Optimal Approach

The key insight is that valid substrings only exist between adjacent groups of identical characters.

Consider the string:

001110000

The groups are:

00 | 111 | 0000

with lengths:

2, 3, 4

Between groups of sizes 2 and 3, we can form:

min(2, 3) = 2

valid substrings.

Between groups of sizes 3 and 4, we can form:

min(3, 4) = 3

valid substrings.

So the answer is:

2 + 3 = 5

Instead of examining every substring directly, we only need to track the sizes of consecutive character groups.

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Generate all substrings and validate each one
Optimal O(n) O(1) Count adjacent character groups and sum minimums

Algorithm Walkthrough

  1. Initialize variables to track the lengths of consecutive character groups.

We maintain:

  • previous_group_length
  • current_group_length
  • result

Initially, the current group length is 1 because the string is non-empty and the first character starts the first group. 2. Traverse the string from left to right starting at index 1.

At each position, compare the current character with the previous character. 3. If the current character matches the previous character, extend the current group.

Example:

000

keeps increasing the current group length. 4. If the current character differs from the previous character, a new group begins.

At this point:

  • The current group becomes the previous group
  • A new current group starts with length 1
  1. Every time we transition between groups, add:
min(previous_group_length, current_group_length)

to the result.

This works because each pair of adjacent groups contributes exactly that many valid substrings. 6. Continue until the entire string has been processed. 7. Return the accumulated result.

Why it works

Every valid substring consists of exactly two consecutive groups of characters. If two adjacent groups have lengths a and b, then the number of balanced substrings formed between them is min(a, b).

The algorithm processes every group exactly once and accumulates the contribution from each adjacent pair. Since every valid substring belongs to exactly one adjacent group pair, the count is complete and correct.

Python Solution

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        previous_group_length = 0
        current_group_length = 1
        result = 0

        for i in range(1, len(s)):
            if s[i] == s[i - 1]:
                current_group_length += 1
            else:
                result += min(previous_group_length, current_group_length)
                previous_group_length = current_group_length
                current_group_length = 1

        result += min(previous_group_length, current_group_length)

        return result

The implementation follows the algorithm directly.

previous_group_length stores the size of the group immediately before the current one. current_group_length tracks the size of the active group while traversing the string.

When consecutive characters match, the current group simply grows larger.

When a character change occurs, the current group ends. At that moment, the algorithm adds the number of valid substrings contributed by the previous adjacent pair using:

min(previous_group_length, current_group_length)

Then the current group becomes the previous group, and a new group starts.

After the loop finishes, one final contribution must be added because the last group transition is not processed inside the loop.

The algorithm uses constant extra memory and only scans the string once.

Go Solution

func countBinarySubstrings(s string) int {
    previousGroupLength := 0
    currentGroupLength := 1
    result := 0

    for i := 1; i < len(s); i++ {
        if s[i] == s[i-1] {
            currentGroupLength++
        } else {
            if previousGroupLength < currentGroupLength {
                result += previousGroupLength
            } else {
                result += currentGroupLength
            }

            previousGroupLength = currentGroupLength
            currentGroupLength = 1
        }
    }

    if previousGroupLength < currentGroupLength {
        result += previousGroupLength
    } else {
        result += currentGroupLength
    }

    return result
}

The Go implementation mirrors the Python solution closely.

Go does not provide a built-in min function for integers, so the code uses explicit comparisons when adding the smaller group length.

Strings in Go are byte slices, and since the input contains only ASCII characters '0' and '1', indexing directly into the string is safe and efficient.

The implementation uses only integer variables and constant extra space.

Worked Examples

Example 1

Input:

s = "00110011"

The groups are:

00 | 11 | 00 | 11

Their lengths are:

2, 2, 2, 2

The algorithm state evolves as follows:

Index Character Current Group Previous Group Added Result
Start 0 1 0 0 0
1 0 2 0 0 0
2 1 1 2 0 0
3 1 2 2 0 0
4 0 1 2 2 2
5 0 2 2 0 2
6 1 1 2 2 4
7 1 2 2 0 4

After traversal:

result += min(2, 2)

Final result:

6

Valid substrings:

0011
01
1100
10
0011
01

Example 2

Input:

s = "10101"

The groups are:

1 | 0 | 1 | 0 | 1

Their lengths are:

1, 1, 1, 1, 1
Index Character Current Group Previous Group Added Result
Start 1 1 0 0 0
1 0 1 1 0 0
2 1 1 1 1 1
3 0 1 1 1 2
4 1 1 1 1 3

After traversal:

result += min(1, 1)

Final result:

4

Valid substrings:

10
01
10
01

Complexity Analysis

Measure Complexity Explanation
Time O(n) The string is traversed exactly once
Space O(1) Only a few integer variables are used

The algorithm is optimal because every character must be examined at least once. No auxiliary data structures proportional to the input size are required.

Test Cases

solution = Solution()

assert solution.countBinarySubstrings("00110011") == 6  # Provided example
assert solution.countBinarySubstrings("10101") == 4  # Alternating characters
assert solution.countBinarySubstrings("0") == 0  # Single character
assert solution.countBinarySubstrings("1") == 0  # Single character
assert solution.countBinarySubstrings("01") == 1  # Smallest valid substring
assert solution.countBinarySubstrings("10") == 1  # Reverse ordering
assert solution.countBinarySubstrings("0011") == 2  # One large and one small substring
assert solution.countBinarySubstrings("000111") == 3  # Equal-sized groups
assert solution.countBinarySubstrings("0001111") == 3  # Unequal-sized groups
assert solution.countBinarySubstrings("11110000") == 4  # Large balanced groups
assert solution.countBinarySubstrings("11111") == 0  # Only one group
assert solution.countBinarySubstrings("00000") == 0  # Only one group
assert solution.countBinarySubstrings("00110") == 3  # Multiple transitions
assert solution.countBinarySubstrings("10101010") == 7  # Fully alternating
assert solution.countBinarySubstrings("000011110000") == 8  # Multiple balanced groups
Test Why
"00110011" Validates the main example
"10101" Tests alternating characters
"0" Smallest possible input
"1" Single-character edge case
"01" Simplest valid substring
"10" Valid substring in reverse order
"0011" Equal adjacent groups
"000111" Larger balanced groups
"0001111" Unequal adjacent groups
"11110000" Large groups with maximum matching
"11111" No valid substrings
"00000" No transitions
"00110" Multiple group transitions
"10101010" Every adjacent pair contributes
"000011110000" Multiple large group interactions

Edge Cases

One important edge case is a string containing only one character, such as "0" or "1". Since a valid substring requires both 0s and 1s, the correct answer is 0. A naive implementation might incorrectly assume every group contributes at least one substring. This implementation handles the case naturally because there is never a second group to pair with the first.

Another important edge case is a string with only one group, such as "11111" or "00000". Even though the string is long, there are no transitions between character types, so no valid substrings exist. The algorithm correctly returns 0 because previous_group_length remains 0 throughout execution.

A more subtle edge case occurs when adjacent groups have different sizes. For example:

0001111

The group sizes are 3 and 4. Only 3 valid substrings can exist because the smaller group limits how many balanced substrings can be formed. Using min(previous_group_length, current_group_length) correctly captures this constraint.

Another tricky case is a fully alternating string like "1010101". Every group has size 1, so every adjacent pair contributes exactly one valid substring. The algorithm handles this efficiently without generating substrings explicitly.