LeetCode 696: Count Binary Substrings Solution in Python – A Step-by-Step Guide

What Is LeetCode 696: Count Binary Substrings?

In LeetCode 696: Count Binary Substrings, you’re given a string s containing only 0s and 1s, and your task is to count the number of substrings that have an equal number of 0s and 1s, where all 0s and all 1s in the substring are grouped consecutively (e.g., "0011" or "10", but not "0101"). Return this count as an integer. For example, with s = "00110011", valid substrings include "01" (twice), "0011" (twice), "10" (twice), totaling 6, so return 6. This problem tests your ability to identify consecutive patterns efficiently.

Problem Statement

• Input:
• s: String of 0s and 1s.
• Output: An integer—number of valid binary substrings.
• Rules:
• Substring must have equal 0s and 1s.
• All 0s and 1s must be consecutive (e.g., "0011", not "0101").
• Count all such substrings in s.

Constraints

• 1 ≤ s.length ≤ 10⁵.
• s[i] is either 0 or 1.

Examples

• Input: s = "00110011"
• Output: 6 (Substrings: "01", "0011", "10", "1100", "01", "10")
• Input: s = "10101"
• Output: 4 (Substrings: "10", "01", "10", "01")
• Input: s = "000"
• Output: 0 (No valid substrings)

These examples set the string—let’s solve it!

Understanding the Problem: Counting Binary Substrings

To solve LeetCode 696: Count Binary Substrings in Python, we need to count substrings in s with equal numbers of consecutive 0s and 1s. A brute-force approach—checking all possible substrings—would be O(n²), inefficient for n ≤ 10⁵. Since we’re looking for consecutive runs of 0s and 1s, grouping these runs and counting pairs can optimize this. We’ll use:

• Best Solution (Grouping Consecutive Runs): O(n) time, O(1) space—fast and elegant.
• Alternative Solution (Brute-Force Substring Check): O(n²) time, O(1) space—simple but slow.

Let’s start with the grouping solution, breaking it down for beginners.

Best Solution: Grouping Consecutive Runs

Why This Is the Best Solution

The grouping consecutive runs approach is the top choice for LeetCode 696 because it’s highly efficient—O(n) time with O(1) space—and uses a clever insight: valid substrings occur at transitions between consecutive runs of 0s and 1s, and their count depends on the minimum length of adjacent runs. It fits constraints (n ≤ 10⁵) perfectly and is intuitive once you see the run logic. It’s like counting handshakes between neighboring groups of 0s and 1s!

How It Works

Think of this as a run counter:

• Step 1: Track Runs:
• Iterate s, count consecutive runs of 0s and 1s.
• Keep prev (previous run length) and curr (current run length).
• Step 2: Count Substrings:
• At each transition (e.g., 0s to 1s), add min(prev, curr) to total.
• This counts all valid substrings ending at the transition.
• Step 3: Update Runs:
• When digit changes, update prev = curr, reset curr = 1.
• Step 4: Return Result:
• Total count of valid substrings.

It’s like a transition tallier—group and count!

Step-by-Step Example

Example: s = "00110011"

• Step 1: Init:
• total = 0, prev = 0, curr = 0.
• Step 2: Process:
• "00": curr = 2.
• "1": total += min(2, 1) = 1, prev = 2, curr = 1.
• "11": curr = 2.
• "0": total += min(2, 1) = 1 (2), prev = 2, curr = 1.
• "00": curr = 2.
• "1": total += min(2, 1) = 1 (3), prev = 2, curr = 1.
• "11": curr = 2.
• End: total += min(2, 2) = 2 (5), prev = 2, curr = 2.
• Step 3: Total = 6.
• Substrings: "00|11" (0011), "0|1" (01), "11|00" (1100), "1|0" (10), "00|11" (0011), "0|1" (01).
• Step 4: Return 6.
• Output: 6.

Example: s = "10101"

• Step 1: Init: total = 0, prev = 0, curr = 0.
• Step 2: Process:
• "1": curr = 1.
• "0": total += min(1, 1) = 1, prev = 1, curr = 1.
• "1": total += min(1, 1) = 1 (2), prev = 1, curr = 1.
• "0": total += min(1, 1) = 1 (3), prev = 1, curr = 1.
• "1": total += min(1, 1) = 1 (4), prev = 1, curr = 1.
• Step 3: Total = 4.
• Substrings: "10", "01", "10", "01".
• Step 4: Return 4.
• Output: 4.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def countBinarySubstrings(self, s: str) -> int:
        # Step 1: Initialize variables
        total = 0
        prev = 0
        curr = 1

        # Step 2: Process string
        for i in range(1, len(s)):
            if s[i] == s[i - 1]:
                curr += 1  # Continue current run
            else:
                total += min(prev, curr)  # Count substrings at transition
                prev = curr  # Previous run complete
                curr = 1     # Start new run

        # Step 3: Add final transition
        total += min(prev, curr)

        # Step 4: Return total count
        return total

• Lines 4-7: Init: Total count, previous and current run lengths.
• Lines 10-15: Process:
• Same digit: Increment curr.
• Different: Add min(prev, curr), update prev, reset curr.
• Line 18: Final transition: Add last pair count.
• Line 21: Return total.
• Time Complexity: O(n)—single pass through string.
• Space Complexity: O(1)—three variables.

This is like a run matcher—group and tally!

Alternative Solution: Brute-Force Substring Check

Why an Alternative Approach?

The brute-force substring check approach iterates all substrings—O(n²) time, O(1) space. It’s simpler for beginners, checking each possible substring for validity, but inefficient for large n. It’s like manually inspecting every piece of the string for a match!

How It Works

Picture this as a substring scanner:

• Step 1: Generate all substrings:
• Iterate start and end indices.
• Step 2: Check validity:
• Count consecutive 0s and 1s, ensure equal and adjacent.
• Step 3: Sum valid counts:
• Increment total for each match.
• Step 4: Return total.

It’s like a substring counter—check and add!

Step-by-Step Example

Example: s = "00110011"

• Step 1: Substrings (partial):
• "00", "001", "0011", "01", "11", "1100", "10", etc.
• Step 2: Check:
• "00": 0s=2, 1s=0, invalid.
• "01": 0s=1, 1s=1, valid, total=1.
• "0011": 0s=2, 1s=2, valid, total=2.
• "11": 0s=0, 1s=2, invalid.
• "1100": 0s=2, 1s=2, valid, total=3.
• "10": 0s=1, 1s=1, valid, total=4.
• Continue: "01" (5), "10" (6).
• Step 3: Total = 6.
• Step 4: Return 6.
• Output: 6.

Code for Brute-Force Approach

Copy codeclass Solution:
    def countBinarySubstrings(self, s: str) -> int:
        # Step 1: Initialize total
        total = 0

        # Step 2: Check all substrings
        for i in range(len(s)):
            for j in range(i + 1, len(s)):
                substring = s[i:j + 1]
                if len(substring) % 2 == 0:  # Must be even length
                    mid = len(substring) // 2
                    zeros = substring[:mid]
                    ones = substring[mid:]
                    if all(c == '0' for c in zeros) and all(c == '1' for c in ones) or \
                       all(c == '1' for c in zeros) and all(c == '0' for c in ones):
                        total += 1

        # Step 3: Return total count
        return total

• Line 4: Init: Total count.
• Lines 7-17: Check:
• Generate substring, check even length, split, validate 0s and 1s.
• Line 20: Return total.
• Time Complexity: O(n²)—check all substrings.
• Space Complexity: O(1)—minimal extra space.

It’s a substring validator—scan and sum!

Comparing the Two Solutions

• Grouping (Best):
• Pros: O(n) time, O(1) space, fast and efficient.
• Cons: Run logic less obvious.
• Brute-Force (Alternative):
• Pros: O(n²) time, O(1) space, straightforward.
• Cons: Much slower.

Grouping wins for efficiency.

Additional Examples and Edge Cases

• Input: s = "0"
• Output: 0 (No valid substring).
• Input: s = "10"
• Output: 1 ("10").

Grouping handles these well.

Complexity Breakdown

• Grouping: Time O(n), Space O(1).
• Brute-Force: Time O(n²), Space O(1).

Grouping is optimal.

Key Takeaways

• Grouping: Run tallying—smart!
• Brute-Force: Substring checking—clear!
• Binary: Counting is fun.
• Python Tip: Loops rock—see Python Basics.

Final Thoughts: Tally Those Substrings

LeetCode 696: Count Binary Substrings in Python is a fun binary challenge. Grouping consecutive runs offers speed and elegance, while brute-force provides a clear baseline. Want more? Try LeetCode 647: Palindromic Substrings or LeetCode 5: Longest Palindromic Substring. Ready to count? Head to Solve LeetCode 696 on LeetCode and find those binary substrings today!