algoadvance

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.

Clarifying Questions

Before getting into the solution, let’s clarify any potential questions:

  1. Input Constraints: What is the maximum length of the string s?
    • The string s’s length can be up to 10^5.
  2. Output: Should the count be the total number of such substrings, or do we need to list them out?
    • We only need to return the total count of such substrings.
  3. Are overlapping substrings allowed?
    • Yes, overlapping substrings are counted as different occurrences.

Strategy

To solve this problem, we will take the following approach:

  1. Group Counting:
    • Traverse the string and count consecutive groups of 0’s and 1’s.
    • Store the counts of these groups in a list.
  2. Count Valid Substrings:
    • Traverse the list of group counts. For every pair of consecutive groups, the number of valid substrings will be the minimum of the counts of the two consecutive groups.

Here’s how we can implement this strategy:

  1. Initialize an empty list to store counts of consecutive 0’s and 1’s.
  2. Traverse through the string while keeping a count of the current character.
  3. When the character changes, append the count to the list and reset the count for the new character.
  4. After populating the list, traverse it to count valid substrings by comparing consecutive group sizes.

Code

def countBinarySubstrings(s: str) -> int:
    groups = []
    count = 1
    
    # Traverse through the string to build the groups list
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            count += 1
        else:
            groups.append(count)
            count = 1
    groups.append(count)  # Append the last group
    
    # Count valid substrings
    valid_substring_count = 0
    for i in range(1, len(groups)):
        valid_substring_count += min(groups[i], groups[i - 1])
    
    return valid_substring_count

Time Complexity

This code efficiently counts the binary substrings by leveraging the grouped nature of consecutive characters and ensures minimal time and space overhead.

Try our interview co-pilot at AlgoAdvance.com