Code Implementation

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        prev_run = 0
        curr_run = 1
        count = 0
        for i in range(1, len(s)):
            if s[i] == s[i-1]:
                curr_run += 1
            else:
                count += min(prev_run, curr_run)
                prev_run = curr_run
                curr_run = 1
        count += min(prev_run, curr_run)
        return count
      

class Solution {
public:
    int countBinarySubstrings(string s) {
        int prev_run = 0, curr_run = 1, count = 0;
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == s[i-1]) {
                ++curr_run;
            } else {
                count += min(prev_run, curr_run);
                prev_run = curr_run;
                curr_run = 1;
            }
        }
        count += min(prev_run, curr_run);
        return count;
    }
};
      

class Solution {
    public int countBinarySubstrings(String s) {
        int prevRun = 0, currRun = 1, count = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i-1)) {
                currRun++;
            } else {
                count += Math.min(prevRun, currRun);
                prevRun = currRun;
                currRun = 1;
            }
        }
        count += Math.min(prevRun, currRun);
        return count;
    }
}
      

var countBinarySubstrings = function(s) {
    let prevRun = 0, currRun = 1, count = 0;
    for (let i = 1; i < s.length; i++) {
        if (s[i] === s[i-1]) {
            currRun++;
        } else {
            count += Math.min(prevRun, currRun);
            prevRun = currRun;
            currRun = 1;
        }
    }
    count += Math.min(prevRun, currRun);
    return count;
};
      

Problem Description

You are given a binary string s (a string consisting only of '0's and '1's). Your task is to count the number of non-empty substrings that have the same number of consecutive '0's and '1's, and all the '0's and all the '1's in these substrings are grouped together. Substrings must be contiguous, and substrings with different starting or ending positions are counted as different, even if they are the same string.

• Each valid substring contains an equal number of consecutive '0's and '1's.
• Within the substring, all '0's must be grouped together and all '1's must be grouped together (e.g., "0011" or "1100" are valid, but "0101" is not).
• Overlapping substrings are allowed.
• The length of s is at least 1 and at most 50,000.

Example:
Input: s = "00110011"
Output: 6
Explanation: There are 6 valid substrings: "0011", "01", "1100", "10", "0011", and "01".

Thought Process

At first glance, you might consider checking every possible substring of s to see if it meets the criteria: equal numbers of grouped '0's and '1's. However, with up to 50,000 characters, this brute-force method would be far too slow.

The key observation is that valid substrings are always formed at the boundaries between runs of '0's and '1's. For example, in "000111", the boundary between the last '0' and the first '1' is where valid substrings start and end. If you can count the lengths of consecutive runs of the same character, you can determine how many valid substrings can be formed at each boundary.

The idea is to process the string in a single pass, keeping track of the lengths of the current run and the previous run. At each transition (when the character changes), the number of valid substrings is increased by the minimum of the previous and current run lengths.

Solution Approach

Let's break down the optimized algorithm step by step:

1. Initialize counters:
   • prev_run to store the length of the previous consecutive group (either '0's or '1's).
   • curr_run to store the length of the current consecutive group.
   • count to store the total number of valid substrings found.
2. Iterate through the string:
   • For each character, compare it to the previous character.
   • If it's the same, increment curr_run.
   • If it's different, it means a new group has started:
     • Add min(prev_run, curr_run) to count. This is because you can only form as many valid substrings as the minimum of the two group sizes.
     • Set prev_run to curr_run, and reset curr_run to 1.
3. Final adjustment:
   • After the loop, add min(prev_run, curr_run) one last time to account for the final group.
4. Return the total count.

This approach ensures that we only make a single pass through the string, making it highly efficient.

Example Walkthrough

Let's walk through the example with s = "00110011":

1. The string can be broken into runs: "00", "11", "00", "11".
2. We track the lengths: [2, 2, 2, 2].
3. At each boundary between runs, count min(prev_run, curr_run):
   • First boundary (between first "00" and first "11"): min(2, 2) = 2
   • Second boundary (between first "11" and second "00"): min(2, 2) = 2
   • Third boundary (between second "00" and second "11"): min(2, 2) = 2
4. Summing up: 2 + 2 + 2 = 6 valid substrings.
5. The substrings are: "0011", "01", "1100", "10", "0011", "01".

At each step, we only need to remember the lengths of the last two runs to determine how many new substrings can be formed.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(N²), since you would examine every possible substring.
  • Space Complexity: O(1), unless you store all substrings.
• Optimized approach (current solution):
  • Time Complexity: O(N), because we only iterate through the string once.
  • Space Complexity: O(1), as we only use a few integer variables for bookkeeping.

The optimized solution is much more efficient and can handle large input sizes easily.

Summary

The "Count Binary Substrings" problem can be solved efficiently by recognizing that valid substrings are always formed at the boundaries between runs of '0's and '1's. By tracking the lengths of these runs as we scan through the string, we can count the number of valid substrings in a single pass using minimal extra space. This approach is both simple and elegant, making it ideal for large input sizes and demonstrating the power of problem-specific observations in algorithm design.