Problem 696

Abstract / Summary

Count the number of substrings with alternating 0s and 1s of equal length in a binary string.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0696.py

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

        previous, same = 0, 1
        for i in range(1, len(s)):
            if s[i] == s[i-1]:
                same   += 1
                result += (same <= previous)
            else:
                previous, same = same, 1
                result += 1

        return result
14 lines | 381 bytes | submitted September 14, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 71% (500k+ submissions).

Typical patterns to solve this problem:
  • String
  • Two Pointers
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a method that counts the number of substrings in a binary string where the substring consists of a block of consecutive 0s followed by an equal-length block of consecutive 1s, or vice-versa. The algorithm processes the input in a single forward pass, maintaining only a few integer variables, and returns the total count directly.

Key Steps

The method begins by establishing a running total named result and two counters, previous and same.

result = 0
previous, same = 0, 1

previous records the length of the most recent contiguous block of identical characters, while same tracks the length of the current block that is being examined. The loop starts from the second character because the first character initiates the first block.

for i in range(1, len(s)):

Inside the loop the algorithm distinguishes two situations:

When the current character matches the previous one - the current block continues, so same is incremented. The algorithm then checks whether the growing block can still form valid substrings with the preceding block. If the size of the current block does not exceed the size of the previous block, a new valid substring is added to result.

if s[i] == s[i-1]:
    same += 1
    result += (same <= previous)

When the current character differs from the previous one - a new block begins. The length of the just-finished block becomes the new previous, and same is reset to 1 for the new character. Because a transition between different characters always creates at least one valid substring (the pair formed by the last character of the previous block and the first character of the new block), result is incremented unconditionally.

else:
    previous, same = same, 1
    result += 1

After the loop finishes, the accumulated result is returned.

return result

Edge Cases Handled

The algorithm gracefully handles an empty input string. Since the loop range starts at 1, the body is never executed and result remains 0, which is the correct count for an empty string.

A single-character string also bypasses the loop, leaving result at 0. No substrings of the required form can exist with only one character, so the output is correct.

When the entire string consists of the same character (e.g., "0000"), the if branch is taken for every iteration. previous stays at 0 because a transition never occurs, and the condition same <= previous is always false. Consequently, result never increments, yielding 0, which matches the expectation that no alternating blocks are present.

For a perfectly alternating pattern such as "010101", each iteration falls into the else branch, resetting previous to the length of the just-finished block (always 1) and adding 1 to result. This produces a count equal to the number of character pairs, correctly reflecting that each adjacent pair forms a valid substring.

Performance Optimizations

The solution achieves linear processing by scanning the string once and updating counters in constant time per character. No auxiliary data structures are allocated; only three integer variables are used throughout, ensuring a minimal memory footprint. The conditional increment result += (same <= previous) leverages the boolean expression directly as an integer (True as 1, False as 0), avoiding an explicit if statement and thereby reducing branching overhead. The early addition of 1 in the transition case captures the guaranteed substring formed by the block boundary without needing additional checks. These choices collectively produce an efficient routine that scales directly with the length of the input.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a long train made of colored blocks, where some are red and some are blue. This code looks at that train to see how many groups of blocks have the same amount of red and blue sitting right next to each other.

The code starts by walking along the train, moving one block at a time. It keeps track of how many blocks of the same color it has seen in a row. It also remembers how many blocks of the other color it just finished looking at.

When it sees a block that is the same color as the one before it, it counts it as part of a growing group. If the current group of one color is not bigger than the group of the other color that came right before it, this counts as a special little match for our collection.

When it finds a block that is a different color, it knows a new group is starting. It sets the number of blocks in the new group to one and starts counting fresh. Because it just switched colors, it knows there is a match between the old group and the new group. All of these matches get added up as the code travels to the end of the train.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 7.67 | σ = 1.39

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java Rust Go TS
LeetcodeHelp C++ Python Java
Progiez C++ Python Java
github BigEggStudy C#
black-shadows C++
charles-wangkai Java
DimitrisJim C
fengvyi C++
fpdjsns C++
halfrost Go
JoshCrozier JS
keineahnung2345 C++
lkwq007 Python
ruoru Rust
suxrobGM C#
trung-hn Python
varunu28 Java
vthwang Java
withaarzoo C++
yuanliu666 Kotlin
YuriSpiridonov Python
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
DimitrisJim C
fengvyi C++
fpdjsns C++
halfrost Go
JoshCrozier JavaScript
keineahnung2345 C++
lkwq007 Python
ruoru Rust
suxrobGM C#
trung-hn Python
varunu28 Java
vthwang Java
withaarzoo C++
yuanliu666 Kotlin
YuriSpiridonov Python
zfang399 C++
38 links | 24 authors | 10 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

3 similar problems

Solved On The Same Day

1 easy 1 medium
3 solutions   September 14, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality