Count Binary Substrings - Leetcode Solution

Problem:

Given a string s, count the number of non-empty 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.

Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".

Note:

s.length will be between 1 and 50,000. s will only consist of "0" or "1" characters.

Solution:

The problem is asking us to count the substrings that satisfy two conditions:

1. the contiguous 0's and 1's are grouped together.
2. the number of contiguous 0's and 1's is the same.

We can start with a simple brute force solution by iterating through all the possible substrings and counting the ones that satisfy the conditions. However, this approach would be very slow and not feasible for larger inputs.

A better approach is to use a two-pointer sliding window approach. We maintain two pointers, left and right, that move together from the start of the string until the end. We keep track of the count of contiguous 0's and 1's as we move along.

When we encounter a transition from 0 to 1 or 1 to 0, we check if the count of 0's and 1's up to that point is the same. If it is, we increment our substrings count by 1.

We continue this process until we reach the end of the string.

Here's the Python code for this approach:

class Solution: def countBinarySubstrings(self, s: str) -> int: count_0, count_1, res = 0, 0, 0 prev_char = None

    for char in s:
        if char == '0':
            if prev_char != '0':
                count_0 = 0
            count_0 += 1
            if count_1 >= count_0:
                res += 1
        else:
            if prev_char != '1':
                count_1 = 0
            count_1 += 1
            if count_0 >= count_1:
                res += 1
        
        prev_char = char
        
    return res

In the code above, we initialize count_0, count_1 and res to 0. We also initialize prev_char to None, which is just a placeholder for the first character in the string so that we don't run into a problem of prev_char being None when we compare it with the current character.

We then loop through each character in the string s and perform the following operations:

1. If the current character is '0', we check if the previous character was also '0', if not, we reset count_0 to 0 and start counting contiguous 0's from the current position.
2. We increment count_0 by 1 for each 0 encountered.
3. We check if the count of 1's encountered so far is greater than or equal to the count of 0's encountered so far. If it is, we increment res by 1 because we have encountered a valid substring.
4. We repeat steps 1 to 3 for character '1'.

Finally, we return the total count of valid substrings.

Time Complexity: O(n), where n is the length of the string s. Space Complexity: O(1), as we are only using constant extra space.

1