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
Difficulty
and has an acceptance rate of about 71% (500k+ submissions).
Typical patterns to solve this problem:
- String
- Two Pointers
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
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
Other Solutions
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++ |
Videos
Similar Problems
- problem 271: Encode and Decode Strings
- problem 2489: Number of Substrings With Fixed Ratio
- problem 3234: Count the Number of Substrings With Dominant Ones
Solved On The Same Day
Extra
- 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