LeetCode 696. 计数二进制子串
目录
题目描述
题意分析
给一个只含 0 和 1 的字符串，要统计有多少个非空子串同时满足两个条件：0 和 1 的个数相同，并且所有的 0 挨在一起、所有的 1 也挨在一起。内容相同但出现位置不同的子串算作多个，不去重。
两个条件合起来的约束比看上去强得多。「0 连续且 1 连续」意味着这个子串只能是「一串 0 后面接一串 1」或者「一串 1 后面接一串 0」这两种形状，中间不允许再交替；再叠加个数相同，形状就被彻底钉死成两段等长的同构块。
约束方面字符串最长五万，$O(n^2)$ 的子串枚举在极端输入下要跑二十多亿次判定，明显不可接受，必须做到一趟扫描。边界上要注意：长度为 1 的输入答案必然是 0；全是同一个字符的输入答案也是 0；扫描结束后最后一段还没被结算，需要单独补一次。
解法：分组计数
核心思路
暴力做法是枚举所有 $O(n^2)$ 个子串，逐个检查是否满足两个条件，总代价 $O(n^3)$ 或优化后的 $O(n^2)$，五万长度直接超时。
瓶颈在于枚举本身：绝大多数子串连「0 连续且 1 连续」这一关都过不了，白白浪费判定。与其枚举子串，不如反过来问「一个合法子串长什么样，它能出现在哪里」。
观察到合法子串必然形如 $0^k1^k$ 或 $1^k0^k$，也就是说它跨过且只跨过一处「相邻两个字符不同」的位置。反过来，给定一处这样的分界点，设它左边的连续同字符段长为 a、右边的连续同字符段长为 b，那么以这个分界点为中心、向两侧各取 k 个字符的子串在 $1 \le k \le \min(a, b)$ 时全部合法，恰好贡献 $\min(a, b)$ 个。不同分界点产生的子串中心不同，绝不会重复计数。
于是问题变成「把字符串切成若干连续同字符段，对每一对相邻段累加较短那段的长度」。真正实现时不需要把所有段长存下来，只要维护两个变量：prev 表示上一段的长度，cur 表示当前正在延伸的这一段的长度。不变量是：扫描到下标 i 时，cur 恒等于以 i 结尾的极长同字符段的长度，prev 恒等于紧挨在它左边那一段的长度（不存在时为 0）。
解题步骤
- 令 prev = 0、cur = 1、total = 0，从下标 1 开始扫描。cur 从 1 起步是因为下标 0 这个字符本身已经构成长度为 1 的段；prev 从 0 起步是因为第一段左边没有段，用 0 保证它不会凭空贡献答案。
- 若
s[i]与s[i-1]相同，说明当前段还在延伸，cur 加一，不结算。- 若两者不同，说明踩到了一个分界点，此时 prev 与 cur 正好是这个分界点左右两段的长度，把 $\min(prev, cur)$ 累加进答案。注意必须先结算再更新，顺序反了 prev 和 cur 会变成同一个值。
- 结算完把 prev 置为 cur、cur 置为 1，让不变量在新段上重新成立。
- 循环结束后再补一次 $\min(prev, cur)$。最后一段是因为字符串结束而终止的，它右边没有分界点触发结算，漏掉这一步就会少算一整对。
以
s = "00110011"走一遍：初始 prev = 0、cur = 1、total = 0。i = 1 时两个字符都是 0，cur 变成 2。i = 2 时字符由 0 变 1，累加 $\min(0, 2) = 0$，total 仍是 0，随后 prev = 2、cur = 1。i = 3 时同为 1，cur 变成 2。i = 4 时字符由 1 变 0，累加 $\min(2, 2) = 2$，total 变成 2，随后 prev = 2、cur = 1。i = 5 时同为 0，cur 变成 2。i = 6 时字符由 0 变 1，累加 $\min(2, 2) = 2$，total 变成 4，随后 prev = 2、cur = 1。i = 7 时同为 1，cur 变成 2。循环结束后补算 $\min(2, 2) = 2$，total 变成 6。对照手工枚举，合法子串是 0011、01、1100、10、0011、01，正好六个。
代码实现
// 相邻两组能形成的合法子串数为 min(prev, cur)。
class Solution {
public int countBinarySubstrings(String s) {
int prev = 0;
int cur = 1;
int total = 0;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == s.charAt(i - 1)) {
cur++;
} else {
total += Math.min(prev, cur);
prev = cur;
cur = 1;
}
}
total += Math.min(prev, cur);
return total;
}
}
// 相邻两组能形成的合法子串数为 min(prev, cur)。
func countBinarySubstrings(s string) int {
prev := 0
cur := 1
total := 0
for i := 1; i < len(s); i++ {
if s[i] == s[i-1] {
cur++
} else {
total += min(prev, cur)
prev = cur
cur = 1
}
}
total += min(prev, cur)
return total
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}
复杂度分析
- 时间复杂度：$O(n)$，其中 n 是字符串长度。每个字符只被读取一次，分界点处的结算是常数级操作。
- 空间复杂度：$O(1)$，只用了 prev、cur、total 三个整型变量，没有存储任何与输入同阶的中间结构。
关键点总结
- 计数题优先考虑「按贡献拆分」：不去枚举答案对象本身，而是找到一个能唯一决定每个答案对象的锚点，再统计每个锚点贡献多少。本题的锚点就是相邻字符不同的分界点。
- 「所有 0 连续且所有 1 连续」这类描述要立刻翻译成形状约束，本题翻译成 $0^k1^k$ 或 $1^k0^k$ 之后，$\min(a, b)$ 这个结论几乎是自明的。
- 分段扫描只需要 prev 与 cur 两个变量就够了，不必真的建出段长数组；能把 $O(n)$ 空间压到 $O(1)$，靠的是「只有相邻两段会互相配对」这条局部性。
- 结算与更新的先后顺序是这类滚动变量写法的通病所在，规则是先用旧状态算完答案，再让状态前进。
- 面试视角：面试官常会先问「暴力怎么写、为什么不行」，再引导到分组；能主动说出「每个合法子串恰好跨过一个分界点，所以不会重复计数」这句唯一性论证，是拿满分的关键，光给出 $\min(a, b)$ 的公式而说不清为什么不重不漏，会被追问到底。
- 面试视角：结尾补算最后一段这个细节，面试官往往会用全同字符或极短串来试探；答题时主动说一句「循环外还要补一次，否则最后一对没人结算」能直接免掉这一轮追问。
易错点总结
- 错误写法：循环结束后忘记补一次
total += min(prev, cur)：s = "00110011"→ 最后一对 00 与 11 从未被结算，返回 4 而不是 6。- 错误写法：cur 初值写成 0：
s = "00110011"→ 第一段的长度被少记一位，第一次结算和后续的 prev 全部偏小，返回 5 而不是 6。- 错误写法：prev 初值写成 1：
s = "0011"→ 相当于在开头凭空多了一段长度为 1 的虚拟段，多贡献了 1，返回 3 而不是 2。- 错误写法：遇到分界点时先写
prev = cur再累加min(prev, cur)：s = "0011"→ 两个变量已经变成同一个值，$\min$ 恒等于当前段长，返回 4 而不是 2。- 错误写法：把每个分界点的贡献写成
prev + cur：s = "0011"→ 把两段的全部长度都当成答案，返回 6 而不是 2。- 错误写法：把题意理解成统计互不相同的合法子串：
s = "00110011"→ 只数出 0011、01、1100、10 这四种，返回 4，而题目明确要求重复出现的子串按次数累计，正确答案是 6。- 错误写法：认为合法子串可以跨越两个以上分界点，于是把三段一起考虑：
s = "000111000"→ 跨两个分界点的子串里 0 被 1 隔成了两截，不满足「所有 0 连续」，把它算进来会让答案超过正确值 6。- 错误写法：循环从 i = 0 开始并直接访问
s[i-1]：任意输入 → 第一次迭代就读到下标 -1，抛出下标越界；正确的起点是 i = 1，把下标 0 的字符交给 cur 的初值来承担。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 485. 最大连续 1 的个数 | 简单 | 只需维护当前段长并取最大值，不涉及相邻段配对 |
| 1446. 连续字符 | 简单 | 同为分段扫描，但求的是最长段而非段间贡献 |
| 443. 压缩字符串 | 中等 | 分段后要原地改写数组，难点在写指针与读指针的错位 |
| 38. 外观数列 | 中等 | 把分段结果重新拼成字符串并迭代多轮 |
| 926. 将字符串翻转到单调递增 | 中等 | 同样围绕 0 与 1 的分界点，但求的是最少翻转次数 |