We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Binary Substrings

Difficulty: Easy

Problem Description

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.

Key Insights

  • The problem requires counting substrings with equal numbers of consecutive 0's and 1's.
  • A valid substring must consist of grouped 0's followed by grouped 1's or vice versa.
  • The approach involves tracking the lengths of consecutive segments of 0's and 1's.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s, since we traverse the string once. Space Complexity: O(1), as we only use a fixed amount of space for counts and indices.

Solution

To solve the problem, we can use an array to store the counts of consecutive 0's and 1's. We iterate through the string to populate this array, and then we use a two-pointer approach to count valid substrings. For each pair of consecutive counts of 0's and 1's, the number of valid substrings is determined by the minimum of the two counts.

Code Solutions

def countBinarySubstrings(s: str) -> int:
    # Initialize the count array
    count = []
    prev_char = ''
    current_count = 0
    
    # Count consecutive characters
    for char in s:
        if char == prev_char:
            current_count += 1
        else:
            if current_count > 0:
                count.append(current_count)
            prev_char = char
            current_count = 1
    count.append(current_count)  # append the last count
    
    result = 0
    # Count valid substrings
    for i in range(1, len(count)):
        result += min(count[i], count[i - 1])
    
    return result
← Back to All Questions