Count Binary Substrings

easy string two pointers

Problem

Given a binary string s, return the number of non-empty substrings that have the same number of 0s and 1s, with all the 0s and all the 1s grouped consecutively.

Inputs = "00110011"

Output6

Valid substrings: "0011", "01", "1100", "10", "0011", "01".

s (0s and 1s)

def count_binary_substrings(s):
    prev, cur, ans = 0, 1, 0
    for i in range(1, len(s)):
        if s[i] == s[i-1]:
            cur += 1
        else:
            ans += min(prev, cur)
            prev, cur = cur, 1
    return ans + min(prev, cur)

function countBinarySubstrings(s) {
  let prev = 0, cur = 1, ans = 0;
  for (let i = 1; i < s.length; i++) {
    if (s[i] === s[i-1]) cur++;
    else { ans += Math.min(prev, cur); prev = cur; cur = 1; }
  }
  return ans + Math.min(prev, cur);
}

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

int countBinarySubstrings(string s) {
    int prev = 0, cur = 1, ans = 0;
    for (int i = 1; i < (int)s.size(); i++) {
        if (s[i] == s[i-1]) cur++;
        else { ans += min(prev, cur); prev = cur; cur = 1; }
    }
    return ans + min(prev, cur);
}

Explanation

A valid substring is something like 0011 or 10: a block of one digit followed by an equal-length block of the other. The key insight is that such substrings only ever live at the boundary between two neighboring runs of equal characters.

So we walk through s measuring run lengths. cur is the length of the run we are currently in, and prev is the length of the run just before it. Whenever s[i] matches the previous character we grow cur; when it changes, a boundary appears.

At each boundary, the number of valid substrings straddling it is min(prev, cur) — you can match up to as many equal characters as the shorter of the two runs allows. We add that to ans, then slide the window: prev = cur and cur = 1.

After the loop we add one final min(prev, cur) for the last boundary, since the loop only counts a pair when it sees the switch.

Example: "00110011" has runs 2,2,2,2. Each adjacent pair contributes min=2, and there are three boundaries, giving 2+2+2 = 6.

Time: O(n) Space: O(1)