Problem

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

Substrings that occur multiple times are counted the number of times they occur.

Examples

Example 1

1
2
3
4
5

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

Example 2

1
2
3

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

Constraints

  • 1 <= s.length <= 10^5
  • s[i] is either '0' or '1'.

Solution

Method 1 – Group Counting 1

Intuition

The key is to count consecutive groups of 0’s and 1’s. For each pair of adjacent groups, the number of valid substrings is the minimum of their lengths. This works because a valid substring must have equal numbers of consecutive 0’s and 1’s, and all 0’s and all 1’s must be grouped together.

Approach

  1. Iterate through the string and count the lengths of consecutive runs of the same character.
  2. For each pair of adjacent runs, add min(length of previous run, length of current run) to the answer.
  3. Return the total count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int countBinarySubstrings(string s) {
        int ans = 0, prev = 0, cur = 1;
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == s[i-1]) {
                cur++;
            } else {
                ans += min(prev, cur);
                prev = cur;
                cur = 1;
            }
        }
        ans += min(prev, cur);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func countBinarySubstrings(s string) int {
    ans, prev, cur := 0, 0, 1
    for i := 1; i < len(s); i++ {
        if s[i] == s[i-1] {
            cur++
        } else {
            if prev < cur {
                ans += prev
            } else {
                ans += cur
            }
            prev = cur
            cur = 1
        }
    }
    if prev < cur {
        ans += prev
    } else {
        ans += cur
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int countBinarySubstrings(String s) {
        int ans = 0, prev = 0, cur = 1;
        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;
            }
        }
        ans += Math.min(prev, cur);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun countBinarySubstrings(s: String): Int {
        var ans = 0
        var prev = 0
        var cur = 1
        for (i in 1 until s.length) {
            if (s[i] == s[i-1]) {
                cur++
            } else {
                ans += minOf(prev, cur)
                prev = cur
                cur = 1
            }
        }
        ans += minOf(prev, cur)
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        ans = 0
        prev = 0
        cur = 1
        for i in range(1, len(s)):
            if s[i] == s[i-1]:
                cur += 1
            else:
                ans += min(prev, cur)
                prev = cur
                cur = 1
        ans += min(prev, cur)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn count_binary_substrings(s: String) -> i32 {
        let s = s.as_bytes();
        let mut ans = 0;
        let mut prev = 0;
        let mut cur = 1;
        for i in 1..s.len() {
            if s[i] == s[i-1] {
                cur += 1;
            } else {
                ans += prev.min(cur);
                prev = cur;
                cur = 1;
            }
        }
        ans += prev.min(cur);
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    countBinarySubstrings(s: string): number {
        let ans = 0, prev = 0, cur = 1;
        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;
            }
        }
        ans += Math.min(prev, cur);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s, as we scan the string once.
  • 🧺 Space complexity: O(1), as only a constant amount of space is used.