Introduction

In this blog post, we will explore how to solve the LeetCode problem "696" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given a binary string s, return 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: s = "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". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: s = "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's. Constraints: 1 <= s.length <= 105 s[i] is either '0' or '1'.

Explanation

Here's an efficient solution to count consecutive binary substrings with equal numbers of 0s and 1s:

• Iterate and Group: The core idea is to iterate through the string, identifying consecutive groups of identical characters (either '0' or '1').
• Count and Compare: Maintain the counts of the current and previous groups. The number of valid substrings formed at each position is the minimum of the current and previous group sizes.

• Accumulate: Sum up the minimums calculated in the previous step to get the total count of valid substrings.

• Runtime Complexity: O(n), where n is the length of the string. Storage Complexity: O(1).

Code

    def countBinarySubstrings(s: str) -> int:
    """
    Counts the number of non-empty substrings with equal numbers of consecutive 0's and 1's.

    Args:
        s: The binary string.

    Returns:
        The number of valid substrings.
    """

    prev_group_len = 0
    curr_group_len = 1
    count = 0

    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            curr_group_len += 1
        else:
            count += min(prev_group_len, curr_group_len)
            prev_group_len = curr_group_len
            curr_group_len = 1

    count += min(prev_group_len, curr_group_len)  # Add the last comparison
    return count