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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Binary Substrings

Number: 696

Difficulty: Easy

Paid? No

Companies: Amazon, Microsoft, J.P. Morgan, Meta, IBM, Salesforce, Google, Meesho, Adobe, Oracle, Goldman Sachs, Helix

Problem Description

Given a binary string s, count the number of non-empty substrings that have the same number of 0's and 1's, and where all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times should be counted as many times as they occur.

Key Insights

  • The substrings we are looking for are periods where a block of 0's is directly followed by a block of 1's (or vice versa).
  • The valid substrings are determined by the minimum length of two consecutive groups.
  • We can solve this problem by compressing the string into a list of counts representing consecutive groups of the same character.
  • The answer is the sum of the min(count[i], count[i+1]) for all valid consecutive groups.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string. Space Complexity: O(n) in the worst-case scenario (when all characters are alternating) which can be optimized to O(1) by processing on the fly.

Solution

We first iterate over the string to count consecutive character groups. Once we have these counts, for each pair of adjacent groups, the number of valid substrings that can be formed is the minimum of the two counts. This works because if a group of 0's is of size x and the following group of 1's is of size y, then there are min(x, y) valid substrings that start in one group and extend into the next.

The solution leverages a two-pass approach (or even a single-pass approach by keeping track of the previous group count) and uses simple arithmetic to compute the final answer.

Code Solutions

# Python solution with clear comments
def countBinarySubstrings(s: str) -> int:
    # List to store counts of consecutive groups
    groups = []
    count = 1  # Start count for the first character

    # Iterate through the string starting from the second character
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            # Same character as previous, increase count
            count += 1
        else:
            # Character changed, append the count of the previous group and reset count
            groups.append(count)
            count = 1
    # Append the count for the last group
    groups.append(count)

    # Now count valid substrings using adjacent group counts
    validSubstrings = 0
    for i in range(1, len(groups)):
        # The number of valid substrings is the minimum of current and previous group counts
        validSubstrings += min(groups[i - 1], groups[i])
    return validSubstrings

# Example usage:
s = "00110011"
print(countBinarySubstrings(s))  # Output: 6
← Back to All Questions