In this approach, we maintain two counters to track consecutive groups of 0's and 1's as we move through the string. By comparing these group counts, we can determine the number of valid equal-length substrings.
As we traverse the string, we increment the count for the current group and check if the previous group length is greater than or equal to the current group length. This indicates that we can form a valid substring.
Time Complexity: O(n) because we make a single pass through the string.
Space Complexity: O(1) since we use a constant amount of extra space.
1#include <iostream>
2#include <string>
3using namespace std;
4
5int countBinarySubstrings(string s) {
6 int prev = 0, curr = 1, count = 0;
7 for (size_t i = 1; i < s.size(); ++i) {
8 if (s[i] == s[i - 1]) {
9 ++curr;
10 } else {
11 count += min(prev, curr);
12 prev = curr;
13 curr = 1;
14 }
15 }
16 return count + min(prev, curr);
17}
18
19int main() {
20 string s = "00110011";
21 cout << countBinarySubstrings(s) << endl;
22 return 0;
23}The C++ solution functions similarly to the C solution, utilizing a single pass to compare current and previous character groups. It uses the min() function to add the smaller of two consecutive group counts, ensuring we count substrings where numbers of '0's and '1's are equal.
This approach involves creating an array to store the lengths of consecutive 0's and 1's. By iterating through this array, we add the minimum value of each pair to a count, which represents valid substrings.
First, traverse the string to form groups, then iterate through the formed group to compute the valid substring count based on consecutive groups' minimum lengths.
Time Complexity: O(n) - The string is traversed twice, but both passes are O(n).
Space Complexity: O(n) due to the need to store group lengths.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int CountBinarySubstrings(string s) {
6 List<int> groups = new List<int>();
7 int count = 0, n = s.Length;
8 int i = 0;
9 while (i < n) {
10 char ch = s[i];
11 int c = 0;
12 while (i < n && s[i] == ch) {
13 i++;
14 c++;
15 }
16 groups.Add(c);
17 }
18
19 for (int j = 1; j < groups.Count; j++) {
20 count += Math.Min(groups[j-1], groups[j]);
21 }
22 return count;
23 }
24
25 public static void Main(string[] args) {
26 Solution sol = new Solution();
27 Console.WriteLine(sol.CountBinarySubstrings("00110011"));
28 }
29}In this C# solution, we create a list containing lengths of consecutive groups of '0's and '1's and compute valid substrings by accumulating the minimum of pairs of adjacent group lengths.