仔细观察发现，连续0与连续1构成的串中其符合条件的子串的数目等于Min(n,m)，n、m分别为连续0和1的个数。
对于这样的问题，解法有很多，简单的一种可以用额外的数组存一下连续0和连续1个数，然后然后遍历数组，统计相邻的最小值即可。
若不用额外空间，考虑的细节就多一点，以下给出了两种相似的解法，细节有所不同。
class Solution {
public int countBinarySubstrings(String s) {
int ans = 0;
int i = 0;
// pre表示之前一段连续1或0个数，cur为当前连续0或1的个数
int pre = 0, cur = 0;
while(i < s.length()){
char c = s.charAt(i);
while(i < s.length() && s.charAt(i) == c){
i++;
cur++;
}
ans += Math.min(pre, cur);
pre = cur;
cur = 0;
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int countBinarySubstrings(String s) {
int ans = 0;
int pre = 0, cur = 1;
for(int i = 1; i < s.length(); i++){
if(s.charAt(i-1) == s.charAt(i)){
cur++;
}else{
ans += Math.min(pre, cur);
pre = cur;
cur = 1;
}
}
// 加上末尾未统计的
ans += Math.min(pre, cur);
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 复杂度分析
时间复杂度：O(1)
空间复杂度：O(1)