🔢 Beginner-Friendly Guide 'Count Binary Substrings' - Problem 696 (C++, Python, JavaScript)

Binary strings can often feel like a puzzle of patterns. This problem challenges you to look beyond the individual bits and identify how groups of consecutive characters interact with one another. Mastering this approach is a great step toward understanding linear string processing and group counting.

Problem Summary

You're given:

• A binary string consisting only of characters '0' and '1'.

Your goal:

• Count the total number of non-empty substrings where the number of 0's and 1's are equal, and all characters of the same type are grouped together consecutively.

Intuition

The core trick to this problem is realizing that we only care about the lengths of consecutive groups. For example, in the string 00011, we have a group of three 0's followed by a group of two 1's.

From these two adjacent groups, how many valid substrings can we form?

1. 01
2. 0011

The number of valid substrings formed by two adjacent groups is always equal to the minimum of the counts of those two groups. If we have three 0's and two 1's, we can only form two valid substrings because we are limited by the smaller group.

Instead of building every possible substring, we simply keep track of the length of the current group of identical characters and the length of the previous group. Every time we move to a new character, if it matches the previous one, our current group grows. If it differs, the old "current" becomes the "previous," and we start a new "current" count at 1.

Walkthrough: Understanding the Examples

Example 1: `s = "00110011"`

1. Start: current = 1 (the first '0'). previous = 0.
2. Index 1 ('0'): Matches previous. current = 2. previous = 0.
3. Index 2 ('1'): Change! previous = 2, current = 1. Since current <= previous, ans = 1 (substring "01").
4. Index 3 ('1'): Matches. current = 2. Since current <= previous, ans = 2 (substring "0011").
5. Index 4 ('0'): Change! previous = 2, current = 1. Since current <= previous, ans = 3 (substring "10").
6. Index 5 ('0'): Matches. current = 2. Since current <= previous, ans = 4 (substring "1100").
7. Index 6 ('1'): Change! previous = 2, current = 1. Since current <= previous, ans = 5 (substring "01").
8. Index 7 ('1'): Matches. current = 2. Since current <= previous, ans = 6 (substring "0011").

Total Result: 6

Code Blocks

C++

class Solution {
public:
    int countBinarySubstrings(string s) {
        int ans = 0, previous = 0, current = 1;
        for (int i = 1; i < s.size(); i++) {
            if (s[i] == s[i - 1]) {
                current++;
            } else {
                previous = current;
                current = 1;
            }
            if (current <= previous) {
                ans++;
            }
        }
        return ans;
    }
};

Python

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        ans = 0
        previous = 0
        current = 1

        for i in range(1, len(s)):
            if s[i] == s[i - 1]:
                current += 1
            else:
                previous = current
                current = 1

            if current <= previous:
                ans += 1

        return ans

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var countBinarySubstrings = function(s) {
    let ans = 0;
    let previous = 0;
    let current = 1;

    for (let i = 1; i < s.length; i++) {
        if (s[i] === s[i - 1]) {
            current++;
        } else {
            previous = current;
            current = 1;
        }

        if (current <= previous) {
            ans++;
        }
    }

    return ans;
};

Key Takeaways

• Group Counting: Many string problems can be simplified by focusing on the lengths of consecutive identical characters rather than the characters themselves.
• Space Optimization: This solution uses extra space because we only store two integers (previous and current) rather than creating an array of all group lengths.
• Linear Complexity: By iterating through the string exactly once, we achieve time complexity, which is optimal for a string of length .

Final Thoughts

This problem is a classic example of how "thinking locally" can solve a global problem. In software engineering, this type of logic is frequently used in Run-Length Encoding (RLE), a simple form of data compression used in early graphics formats and fax machines. Understanding how to process streams of data in a single pass is a vital skill for high-performance systems and technical interviews alike.