Count Binary Substrings

Problem

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.

Constraints

• 1 <= s.length <= 105
• s[i] is either '0' or '1'.

Solution

The problem Count Binary Substrings can be solved by counting consecutive 0’s and 1’s. Let ai be a bit on a ith index with a value of 0 and bi with a value of 1. Then the number of non-empty substrings that have the same number of 0’s and 1’s for a consecutive substring aiai+1...ai+m-1bi+mbi+m+1...bi+m+n-1 becomes min(m, n). As this also holds true for a transition from consecutive 1’s to 0’s, we can iterate through the given string only once and find all non-empty substrings that have the same number of 0’s and 1’s.

Implementation

class Solution
{
  public:
    int countBinarySubstrings(string s)
    {
        char bit = s.front();
        int prev = 0, cur = 0;

        int ret = 0;
        for (char ch : s)
        {
            if (ch != bit)
            {
                ret += min(prev, cur);
                bit = ch;
                prev = cur;
                cur = 0;
            }
            cur += 1;
        }

        return ret + min(prev, cur);
    }
};