LeetCode 696 Count Binary Substrings

LeetCode

Give 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.

Example 1:

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:

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<sup>5</sup> s[i] is either '0' or '1'.

题目大意：

子串中，连续0和连续1的个数中间对称，求这样的子串的个数

算法思路：

这题至少medium，一开始考虑给定一个字符串怎么判断是否满足条件，统计个数和flag变化。然后是双重循环分别以a[0..n-1]为开头的子串判断，若不满足就跳出内循环，复杂度为O(n).
既然是连续，又是只有0和1，不妨考虑统计个数。如00110011,统计0和1的个数为count=[2,2,2,2]相邻的数代表不同种类，所以去min(count[i-1], count[i])，如2, 2可以是01/10, 0011/1100两种，具体以哪个数开始取决于数组本身。统计i=[1..n-1]即所求。复杂度为O(n).

注意事项：

1. 累计思想，按0和1累计得到累计数组，然后求相邻最小个数的和。
2. 循环出来，处理最后一个部分。

Python代码：

def countBinarySubstrings(self, s: str) -> int:
	presum, count, res = [], 1, 0
	for i in range(1, len(s)): #
		if s[i - 1] == s[i]:
			count += 1
		else:
			presum.append(count) #[2, 2,2,2]
			count = 1
	if count > 0:
		presum.append(count)
	for i in range(1, len(presum)):
		res += min(presum[i - 1], presum[i])
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)