Solution Explanation

This problem asks us to count the number of substrings within a binary string (s) that meet two conditions:

1. Equal Number of 0s and 1s: The substring must contain an equal number of 0s and 1s.
2. Grouped Consecutively: All 0s must be grouped together, and all 1s must be grouped together. This means there can't be any interleaving of 0s and 1s within the substring.

The most efficient approach uses a two-pointer technique, or more accurately, it iterates through the string to count consecutive occurrences of each digit and then uses those counts to find the number of qualifying substrings.

Algorithm:

1. Count Consecutive Digits: Iterate through the input string s. Count the number of consecutive occurrences of each digit (0 or 1). Store these counts in a list (e.g., t).

2. Calculate Substrings: Iterate through the list t. For each pair of adjacent counts (t[i-1] and t[i]), the minimum of these two counts represents the number of valid substrings that can be formed using those consecutive groups of 0s and 1s. Add this minimum to the total count (ans).

Example:

Let's take the example s = "00110011".

1. Count Consecutive Digits:

   • The first group is "00" (count = 2).
   • The second group is "11" (count = 2).
   • The third group is "00" (count = 2).
   • The fourth group is "11" (count = 2). Therefore, t = [2, 2, 2, 2].

2. Calculate Substrings:

   • min(t[0], t[1]) = min(2, 2) = 2 (Substrings: "0011", "01")
   • min(t[1], t[2]) = min(2, 2) = 2 (Substrings: "1100", "10")
   • ans = 2 + 2 = 4

   However, we have not accounted for the fact that substrings like "0011" are counted twice in this method. The above logic will actually calculate all possible substrings that match the grouped consecutive condition. To correct this, we can modify the final loop as follows:

   • ans = 2 + 2 = 4. This counts "0011" and "01" (from the first two elements) correctly, and "1100" and "10" (from the next two elements) correctly, giving a total of 4 valid substrings. This is corrected by considering the total number of substrings between consecutive runs of digits.

Time Complexity: O(n), where n is the length of the string. We iterate through the string once to count consecutive digits and then iterate through the list of counts (which has a length at most n/2).

Space Complexity: O(k), where k is the number of groups of consecutive digits. In the worst case, k could be n (e.g., "010101..."), but on average, it will be much smaller. This space is used to store the list t.

Code in Different Languages

The code provided earlier demonstrates the algorithm in Python, Java, C++, and Go. Here's a breakdown focusing on the core logic, similar to the comments in the earlier code:

Python:

def countBinarySubstrings(s: str) -> int:
    groups = []
    count = 1
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            count += 1
        else:
            groups.append(count)
            count = 1
    groups.append(count) # Add the last group
 
    ans = 0
    for i in range(1, len(groups)):
        ans += min(groups[i - 1], groups[i])
    return ans
 

Java:

class Solution {
    public int countBinarySubstrings(String s) {
        List<Integer> groups = new ArrayList<>();
        int count = 1;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                count++;
            } else {
                groups.add(count);
                count = 1;
            }
        }
        groups.add(count);
 
        int ans = 0;
        for (int i = 1; i < groups.size(); i++) {
            ans += Math.min(groups.get(i - 1), groups.get(i));
        }
        return ans;
    }
}

C++:

class Solution {
public:
    int countBinarySubstrings(string s) {
        vector<int> groups;
        int count = 1;
        for (int i = 1; i < s.length(); i++) {
            if (s[i] == s[i - 1]) {
                count++;
            } else {
                groups.push_back(count);
                count = 1;
            }
        }
        groups.push_back(count);
 
        int ans = 0;
        for (size_t i = 1; i < groups.size(); i++) {
            ans += min(groups[i - 1], groups[i]);
        }
        return ans;
    }
};

Go:

func countBinarySubstrings(s string) int {
	groups := []int{}
	count := 1
	for i := 1; i < len(s); i++ {
		if s[i] == s[i-1] {
			count++
		} else {
			groups = append(groups, count)
			count = 1
		}
	}
	groups = append(groups, count)
 
	ans := 0
	for i := 1; i < len(groups); i++ {
		ans += min(groups[i-1], groups[i])
	}
	return ans
}
 
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

All these codes follow the same fundamental algorithm. They differ only in syntax and minor library usage specifics for each language. The core logic of counting consecutive digits and then calculating the minimum between adjacent counts remains consistent.