文章目录
题目
标题和出处
标题：计数二进制子串
出处：696. 计数二进制子串
难度
4 级
题目描述
要求
给定一个二进制字符串 s \texttt{s} s，计算具有相同数量的 0 \texttt{0} 0 和 1 \texttt{1} 1 并且所有 0 \texttt{0} 0 和所有 1 \texttt{1} 1 都是连续的非空子字符串的数量。
重复出现的子串要计算它们出现的次数。
示例
示例 1：
输入：
s
=
"00110011"
\texttt{s = "00110011"}
s = "00110011"
输出：
6
\texttt{6}
6
解释：有
6
\texttt{6}
6 个子串具有相同数量的连续
1
\texttt{1}
1 和
0
\texttt{0}
0：
"0011"
\texttt{"0011"}
"0011"，
"01"
\texttt{"01"}
"01"，
"1100"
\texttt{"1100"}
"1100"，
"10"
\texttt{"10"}
"10"，
"0011"
\texttt{"0011"}
"0011" 和
"01"
\texttt{"01"}
"01"。
请注意，一些重复出现的子串要计算它们出现的次数。
另外，
"00110011"
\texttt{"00110011"}
"00110011" 不是有效的子串，因为所有的
0
\texttt{0}
0（和
1
\texttt{1}
1）没有组合在一起。
示例 2：
输入：
s
=
"10101"
\texttt{s = "10101"}
s = "10101"
输出：
4
\texttt{4}
4
解释：有
4
\texttt{4}
4 个子串具有相同数量的连续
1
\texttt{1}
1 和
0
\texttt{0}
0：
"10"
\texttt{"10"}
"10"，
"01"
\texttt{"01"}
"01"，
"10"
\texttt{"10"}
"10"，
"01"
\texttt{"01"}
"01"。
数据范围
- 1 ≤ s.length ≤ 10 5 \texttt{1} \le \texttt{s.length} \le \texttt{10}^\texttt{5} 1≤s.length≤105
- s[i] \texttt{s[i]} s[i] 是 ‘0’ \texttt{`0'} ‘0’ 或 ‘1’ \texttt{`1'} ‘1’
解法
思路和算法
可以将字符串 s s s 分组，每一组只包含相同字符且相邻两组包含的字符不同。例如， s = ‘ ‘ 000011100 " s = ``000011100" s=‘‘000011100" 可以分成 3 3 3 组： ‘ ‘ 0000 " ``0000" ‘‘0000"、 ‘ ‘ 111 " ``111" ‘‘111"、 ‘ ‘ 00 " ``00" ‘‘00"。
如果一个子串满足具有相同数量的 0 0 0 和 1 1 1 并且所有 0 0 0 和所有 1 1 1 都连续，则该子串满足以下两个条件：
-
该子串的长度为偶数；
-
该子串的前一半都是 0 0 0，后一半都是 1 1 1，或者前一半都是 1 1 1，后一半都是 0 0 0。
将字符串 s s s 分组之后，满足上述条件的子串一定是跨越相邻的两个分组的某个子串。假设相邻的两个分组的长度分别是 x x x 和 y y y，跨越这两个分组的子串包含 z z z 个 0 0 0 和 z z z 个 1 1 1，则有 1 ≤ z ≤ min ( x , y ) 1 \le z \le \min(x, y) 1≤z≤min(x,y)，即跨越这两个分组的子串的数量是 min ( x , y ) \min(x, y) min(x,y)，它们的长度分别是从 2 2 2 到 2 × min ( x , y ) 2 \times \min(x, y) 2×min(x,y) 的全部偶数。
由此可以得到：跨越两个相邻的分组的子串数量是这两个分组的大小中的较小值。
基于上述结论，可以得到如下解法：遍历字符串 s s s 并得到每个分组的大小，然后遍历每一对相邻的分组，将其中的较小的分组大小加到答案中，遍历结束后即可得到答案。
具体实现时，只需要遍历 s s s 一次即可。遍历过程中判断相邻的两个字符是否相同，若相同则将当前分组的大小加 1 1 1，若不同则说明一个分组遍历结束，比较遍历结束的分组和更前面的分组的大小，将其中的较小的分组大小加到答案中，遍历 s s s 结束时需要对最后一个分组再次计算，避免遗漏。
代码
class Solution {
public int countBinarySubstrings(String s) {
int count = 0, prev = 0, curr = 1;
int length = s.length();
for (int i = 1; i < length; i++) {
if (s.charAt(i - 1) == s.charAt(i)) {
curr++;
} else {
count += Math.min(prev, curr);
prev = curr;
curr = 1;
}
}
count += Math.min(prev, curr);
return count;
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是字符串 s s s 的长度。需要遍历字符串 s s s 一次。
-
空间复杂度： O ( 1 ) O(1) O(1)。