Count Binary Substrings

Tagged: Two Pointers, String, Array

Problem#

Given a binary string, 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 must be grouped consecutively.

The substrings can occur more than one and will still be counted.

Below are some of the examples:

Input: "00110011"
Output: 6
Explanation: The substrings are "0011", "01", "1100", "10", "0011", and "01".
Notice that some of these substrings repeat and are counted the number of times they occur.
"00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

Input: "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

This tutorial will show you some algorithms that can be used to solve this problem.

Solution#

Group by Character#

When the string is like 00011, then the total number of substrings is the minimum number of duplicates (2 in example above).
Now, if there is a switch (0 to 1) or (1 to 0), we need to compare previous total and current total.
So, for string like 000110000. We can create array to group total number of consecutive character. In this case, it will be groups = [3,2,4],
Then, start from index 1, we compare current number with previous number we will get min(3,2) + min(2,4) = 2 + 2 = 4.

public int CountBinarySubstrings(string s)
{
    int[] groups = new int[s.Length];
    groups[0] = 1;
    int t = 0;
    for (int i = 1; i < s.Length; i++)
    {
        if (s[i - 1] != s[i])
        {
            groups[++t] = 1;
        }
        else
        {
            groups[t]++;
        }
    }

    int ans = 0;
    for (int i = 1; i <= t; i++)
    {
        ans += Math.Min(groups[i - 1], groups[i]);
    }

    return ans;
}

Time Complexity O(n) and Space Complexity O(n) because of the array groups.

Two Pointers (One Pass)#

This algorithm is the improvement of previous algorithm where we use two pointers named prev and curr that will track total number of consecutive characters in current and previous groups.

int ans = 0;
int prev = 0;
int curr = 1;
for (int i = 1; i < s.Length; i++)
{
    if (s[i - 1] != s[i])
    {
        ans += Math.Min(prev, curr);
        prev = curr;
        curr = 1;
    }
    else
    {
        curr++;
    }
}

return ans += Math.Min(prev, curr);

Time Complexity O(n) and Space Complexity O(1) because it doesn’t use additional storage.