Problem Statement in English

You’re given a binary string s. You have to count the number of non-empty (contiguous) substrings that have the same number of 0s and 1s, and all the 0s and all the 1s in these substrings are grouped consecutively.

Return the number of such substrings.

Approach

Thinking about the problem in terms of a current group and a previous group helps with both code structuring and the solution itself.

As we iterate we update the current group count and whenever we encounter a different character, we know that the current group has ended.

We then update the result with the minimum of the previous and current group counts, because that will be the number of substrings that satisfy the criteria given by the question.

This is because a valid substring can only be formed by pairing characters from the previous and current groups.

We then update the previous group count to be the current group count and reset the current group count to 1 (since we have just encountered a different character).

And at the end of the iteration, we need to do one final update to the result to account for any valid substrings that may be formed by the last group.

And we’re done!

Solution in Python


class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        res = 0
        l = len(s)

        prevGroup = currGroup = 0

        for i in range(l):
            if s[i] != s[i - 1]:
                res += min(prevGroup, currGroup)
                prevGroup = currGroup
                currGroup = 1
            else:
                currGroup += 1

        res += min(prevGroup, currGroup)
        prevGroup = currGroup
        currGroup = 0

        return res

Complexity

  • Time: $O(n)$

  • Space: $O(1)$
    Since we’re only using a constant amount of space to store the result and the group counts.

And we are done.