计数二进制子串 图解题解

要数的是哪一种子串

给一个只有 0 和 1 的字符串 s，数出有多少个子串（连续的一段字符）满足 0 和 1 个数相等、且所有 0 挨在一起、所有 1 也挨在一起。题面例子 s = "00110011"，答案 6，"01"、"0011"、"1100" 都算，位置不同的相同子串各算一个；"0101" 这种来回交替的不算，没做到每种字符各自连续。

把每个子串截出来验一遍，慢在哪

长 n 的字符串有大约 n²／2 个子串，逐个截出来既数两种字符是否等量、又查是否各自连续，光子串就 O(n²) 个，每个再花 O(n)，合起来 O(n³)。s 一长到十万级就跑不完，得找不逐串枚举的做法。

为什么合法子串只能卡在两段交界上

把 s 按连续相同字符切段，"00110011" 就是 00、11、00、11 四段。合法子串左半全是一种字符、右半全是另一种，中间只跨一个「段与段的交界」——跨两个交界，中间必冒出第三段，某种字符就断开、不再连续。所以每个合法子串都夹在相邻两段之间。

相邻两段设长度为 a 和 b，合法子串是「左边取几个、右边就取同样几个」，从 1 个到较短那段用光，一共 min(a, b) 个。两段各 2 个字符，能拼出 "01" 和 "0011"。把每对相邻段的 min 加起来就是答案。

一遍扫描怎么切段、边切边累加

不必把段长存成数组，两个变量就够。i 指向当前段开头，j 从 i 后一位出发，只要 s[j] 和 s[i] 相同就往右走，停下时这段长度 cur = j − i。用 pre 记前一段长度，每切出一段就把 ans 加上 min(pre, cur)，再把 pre 换成 cur，i 跳到 j 开下一段。

两处得盯住：贡献取 min 不是相加，合法子串两侧必须一样长、被较短那段卡死；结算完必须 pre = cur，下一段要配的是刚封口这段的长度，忘了换就拿旧值去配。第一段前面没有段，pre 起始为 0，min(0, cur) 是 0，只把长度交给 pre。

"00110011" 切成四段，6 是一步步加出来的

整串切成四段，长度都是 2。第一段 "00"：pre=0、cur=2，ans 加 min(0, 2)=0，pre 更新成 2。往后三段 cur 都是 2，每段 ans 加 min(2, 2)=2、pre 保持 2：第二段到 2，第三段到 4，第四段到 6。扫到末尾返回 6。

数着数着多出一倍，问题都出在结算那一步

最常见的错是把贡献写成 pre + cur、两段直接相加，六个子串一下变十几个——合法子串两边等长，只能被较短那段限制，取 min 不取和。其次是结算后忘了 pre = cur，下一段拿着旧长度去配，min 算在错的数上。还有内层没把相同字符走到底就结算，段没封口、cur 少数几个，往后全错。

时间上 i 和 j 都只朝右走、各扫一遍，O(n)；只用 pre、cur、ans 几个变量，空间 O(1)。边界也想清：空串没有段，答案 0；整串同字符如 "0000" 只一段、配不成对，也是 0；最短一对 "01" 给出 1。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        n = len(s)
        ans = i = 0
        pre = 0
        while i < n:
            j = i + 1
            while j < n and s[j] == s[i]:
                j += 1
            cur = j - i
            ans += min(pre, cur)
            pre = cur
            i = j
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int countBinarySubstrings(string s) {
        int n = s.size();
        int ans = 0;
        int i = 0;
        int pre = 0;
        while (i < n) {
            int j = i + 1;
            while (j < n && s[j] == s[i]) {
                ++j;
            }
            int cur = j - i;
            ans += min(pre, cur);
            pre = cur;
            i = j;
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int countBinarySubstrings(String s) {
        int n = s.length();
        int ans = 0;
        int i = 0;
        int pre = 0;
        while (i < n) {
            int j = i + 1;
            while (j < n && s.charAt(j) == s.charAt(i)) {
                j++;
            }
            int cur = j - i;
            ans += Math.min(pre, cur);
            pre = cur;
            i = j;
        }
        return ans;
    }
}