In this article, we will deep dive into ‘Count Binary Substrings’ problem on Leetcode and discuss how to solve it in Python.
The problem, titled ‘Count Binary Substrings’ on Leetcode, reads as follows:
Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.
Substrings that occur multiple times are counted the number of times they occur.
For example, given the string
s = "00110011", there are
6 substrings that have equal number of consecutive
Given another string
s = "10101", there are
Understanding the Problem
Before we go about devising a solution, we must fully understand what the problem asks of us. We are required to count all non-empty substrings of the input string where the number of
0s equals the number of
1s, and all
0s and all
1s are grouped together without interruption.
Brute Force Approach
One way to solve this problem is by using a brute force approach where we check every possible substring of the string
s. For each substring, we check if it meets our conditions, i.e., it has the same number of consecutive
1s. If it does, we increase our count. However, this approach would be highly inefficient with a time complexity of O(n^2) due to nested loops required to generate substrings and check each one.
An optimized solution involves linear scanning. As we scan the string, we need to keep track of the number of
0s we have seen grouped consecutively (let’s call this
current_count), and also the number we saw in the last group (let’s call this
Whenever the character we are scanning changes (from
0 or vice versa), we have a chance to form a new valid substring. The smaller count of the last group and the current group gives the number of new valid substrings. The reason is that a valid substring cannot have more
0s) than the group they are part of.
Now, let’s write a Python function
countBinarySubstrings that implements the optimized approach:
def countBinarySubstrings(s): previous_count = current_count = 1 result = 0 for i in range(1, len(s)): if s[i] == s[i-1]: # Continue counting the group current_count += 1 else: # New group starts previous_count = current_count current_count = 1 if previous_count >= current_count: # Valid substring possible result += 1 return result
Testing the Solution
We can test our solution with some test cases:
print(countBinarySubstrings("00110011")) # Returns 6 print(countBinarySubstrings("10101")) # Returns 4 print(countBinarySubstrings("100111001")) # Returns 6
countBinarySubstrings function should return
6 for the input
4 for the input
6 for the input
The ‘Count Binary Substrings’ problem on LeetCode is a fascinating problem that involves a blend of string manipulation and dynamic programming. We tackled this problem in Python, starting with a brute force approach and then optimizing it by observing the patterns in the problem.