## 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 `0`

s equals the number of `1`

s, and all `0`

s and all `1`

s 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 `0`

s and `1`

s. 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 `1`

s or `0`

s 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 `1`

s (or `0`

s) 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.