696. 计数二进制子串
题目描述
输入一个只由 '0' 和 '1' 组成的字符串 s。
统计满足以下条件的非空连续子串的个数：子串中 0 和 1 的数量相同，并且所有 0 挤在一起、所有 1 也挤在一起，例如 "0011"、"10"。
内容相同但位置不同的子串要分别计数。
示例 1
输入：s = "00110011" 输出：6
解释：符合条件的有 "0011"、"01"、"1100"、"10"、"0011"、"01"，共 6 个。
示例 2
输入：s = "10101" 输出：4
解释：符合条件的是两个 "10" 和两个 "01"。
数据范围
1 <= s.length <= 10^5s[i]为'0'或'1'。
解题思路
符合要求的子串一定横跨两个相邻的“连续段”：前半是一段的末尾，后半是下一段的开头。相邻两段长度为 prev 和 cur 时，可以取 1+1、2+2、…，最多到 min(prev, cur)，所以贡献 min(prev, cur) 个。用双指针划分连续段：i 指向一段开头，j 向右走到字符变化处，j - i 就是这一段的长度，然后 i = j 进入下一段。
为什么正确
处理完一段后，ans 等于完全位于 s[0..j) 内的合法子串个数，prev 是刚结束的那一段的长度。
复杂度分析
时间 O(n)，j 只向右走；额外空间 O(1)。
易错点
不要枚举所有子串（O(n^2) 会超时）；注意是取 min 而不是把两段长度相加，第一段没有前一段，prev 初始为 0。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def countBinarySubstrings(self, s: str) -> int:
n = len(s)
ans = 0
prev = 0
i = 0
while i < n:
j = i
while j < n and s[j] == s[i]:
j += 1
cur = j - i
ans += min(prev, cur)
prev = cur
i = j
return ansclass Solution {
public int countBinarySubstrings(String s) {
int n = s.length();
int ans = 0;
int prev = 0;
int i = 0;
while (i < n) {
int j = i;
while (j < n && s.charAt(j) == s.charAt(i)) {
j++;
}
int cur = j - i;
ans += Math.min(prev, cur);
prev = cur;
i = j;
}
return ans;
}
}class Solution {
public:
int countBinarySubstrings(string s) {
int n = s.size();
int ans = 0;
int prev = 0;
int i = 0;
while (i < n) {
int j = i;
while (j < n && s[j] == s[i]) {
j++;
}
int cur = j - i;
ans += min(prev, cur);
prev = cur;
i = j;
}
return ans;
}
};func countBinarySubstrings(s string) int {
n := len(s)
ans := 0
prev := 0
i := 0
for i < n {
j := i
for j < n && s[j] == s[i] {
j++
}
cur := j - i
if prev < cur {
ans += prev
} else {
ans += cur
}
prev = cur
i = j
}
return ans
}var countBinarySubstrings = function(s) {
const n = s.length;
let ans = 0;
let prev = 0;
let i = 0;
while (i < n) {
let j = i;
while (j < n && s[j] === s[i]) {
j++;
}
const cur = j - i;
ans += Math.min(prev, cur);
prev = cur;
i = j;
}
return ans;
};function countBinarySubstrings(s: string): number {
const n = s.length;
let ans = 0;
let prev = 0;
let i = 0;
while (i < n) {
let j = i;
while (j < n && s[j] === s[i]) {
j++;
}
const cur = j - i;
ans += Math.min(prev, cur);
prev = cur;
i = j;
}
return ans;
}