Leetcode – Count Binary Substrings Solution in Python

Spread the love

Introduction

In this article, we will deep dive into ‘Count Binary Substrings’ problem on Leetcode and discuss how to solve it in Python.

Problem Statement

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 1‘s and 0‘s: "0011", "01", "1100", "10", "0011", and "01".

Given another string s = "10101", there are 4 substrings: "10", "01", "10", and "01".

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.

Solution

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 0s and 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.

Optimized Approach

An optimized solution involves linear scanning. As we scan the string, we need to keep track of the number of 1s or 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 previous_count).

Whenever the character we are scanning changes (from 1 to 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 1s (or 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

The countBinarySubstrings function should return 6 for the input "00110011", 4 for the input "10101", and 6 for the input "100111001".

Conclusion

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.

Leave a Reply