696. Count Binary Substrings #

Problem #

Give a string s, count the number of non-empty (contiguous) 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.

Example 1:

Input: "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 becauseall the 0's (and 1's) are not grouped together.

Example 2:

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

Note:

• s.length will be between 1 and 50,000.
• s will only consist of “0” or “1” characters.

Problem Statement #

Given a string s, count the number of non-empty (contiguous) substrings that have the same number of 0s and 1s, and all the 0s and all the 1s in these substrings are consecutive. Substrings that occur multiple times should be counted the number of times they occur.

Solution Approach #

• Easy problem. First group and count the number of 0s and 1s. For example, for 0110001111, the grouped counts by 0s and 1s are [1, 2, 3, 4]. Then construct the result. For every 2 adjacent groups, take the smaller count. For example, for 0110001111, the result should be min(1,2), min(2,3), min(3,4), namely 01, 01, 10, 1100, 0011, 000111. Time complexity is O(n), space complexity is O(1).

Code #

package leetcode

func countBinarySubstrings(s string) int {
	last, res := 0, 0
	for i := 0; i < len(s); {
		c, count := s[i], 1
		for i++; i < len(s) && s[i] == c; i++ {
			count++
		}
		res += min(count, last)
		last = count
	}
	return res
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}