LeetCode 696. 计数二进制子串
题目描述
题意分析
统计连续子串：其中 0 和 1 的数量相同，而且所有 0 连成一段、所有 1 连成一段。也就是先一段 0 再等长的一段 1，或顺序相反。相同内容出现在不同位置时分别计数。
解法：分组计数
核心思路
[!blue]
将相同的连续字符看作一段。合法子串只能跨越一个字符变化的边界，否则某种字符会被另一种字符隔开，不再各自连续。因此只需考虑相邻的两段。
设相邻段长为
a、b。要在它们之间形成合法子串，必须取前一段末尾的t个字符和后一段开头的t个字符。每个t都唯一确定一个连续窗口，而t可以从 1 取到min(a, b)，所以这条边界恰好贡献min(a, b)个答案。每个合法子串只有一个变化边界，会且只会在那一对相邻段中被计数。于是答案就是所有相邻段长的较小值之和；不必保存全部段长，只保留上一段长度
prev和当前段长度cur。扫描遇到字符变化时，当前段已经结束，先累加
min(prev, cur)，再把当前段变为上一段，并令新段长度为 1。到字符串末尾时没有新的字符变化来触发结算，因此循环后还要补上最后一对。
解题步骤
- 题目保证字符串非空，初始化
prev = 0、cur = 1、total = 0。- 从第二个字符开始扫描。与前一个字符相同，就令
cur++。- 字符不同时，先累加
min(prev, cur)，再令prev = cur、cur = 1。- 扫描结束后再累加一次
min(prev, cur)，返回总数。第一段没有前一段，初始
prev = 0会使它的单独贡献为 0。单字符或全部字符相同的字符串也会自然得到 0。
代码实现
// 相邻两组能形成的合法子串数为 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)$，一趟分段扫描。
- 空间复杂度：$O(1)$，仅保存相邻两段长度。
关键点总结
[!green]
- 按唯一的字符变化边界分类，将子串计数化为相邻段长计算。
- 固定每侧长度后，窗口必须紧贴边界，所以一对段的贡献是较短段长，而不是段长乘积。
- 新段开始时结算的是刚结束的段与它前一段，最后一对需单独补算。
易错点总结
[!yellow]
- 只统计 0 和 1 的总数相同，会接受字符多次交替、没有各自成组的子串。
- 结算前就覆盖
prev或cur，会丢失相邻两段的真实长度。- 忘记循环后的结算，会漏掉末尾两段之间的所有答案。
- 对子串内容去重会少算，不同位置的出现次数都必须保留。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 443. 压缩字符串 | 中等 | 按游程分组可以得到相邻两段长度，本题累加它们的较小值而非输出压缩字符串。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！