一、题目大意

给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组连续的。

重复出现（不同位置）的子串也要统计它们出现的次数。

示例 1：

输入：s = "00110011"输出：6 解释：6 个子串满足具有相同数量的连续 1 和 0 ："0011"、"01"、"1100"、"10"、"0011" 和 "01" 。注意，一些重复出现的子串（不同位置）要统计它们出现的次数。另外，"00110011" 不是有效的子串，因为所有的 0（还有 1 ）没有组合在一起。

示例 2：

输入：s = "10101"输出：4 解释：有 4 个子串："10"、"01"、"10"、"01" ，具有相同数量的连续 1 和 0 。

提示：

• 1 <= s.length <= 105

• s[i] 为 '0' 或 '1'

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/count-binary-substrings著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、解题思路

思路 1:从左往右遍历数组，记录和当前位置数字相同中且连续的长度，以及其之前连续的不同数字的长度。举例来说，对于 00110 的最后一位，我们记录的相同数字长度是 1，因为只有一个连续 0；我们记录的不同数字长度是 2，因为在 0 之前有两个连续的 1。若不同数字的连续长度大于等于当前数字的连续长度，则说明存在一个且只存在一个当前数字结尾的满足条件的子字符串。

思路 2:还可以从字符串的每个位置开始，向左向右延长，判断存在多少当前位置为中轴的由 01 连续二进制字符串。

三、解题方法

3.1 Java 实现

public class Solution {    public int countBinarySubstrings(String s) {        // 输入：s = "00110011"        // 输出：6        int ans = 0;        for (int i = 0; i < s.length() - 1; i++) {            ans += extendSubstrings(s, i, i + 1);        }        return ans;    }
    private int extendSubstrings(String s, int l, int r) {        char lc = s.charAt(l);        char rc = s.charAt(r);        if (!((lc == '1' && rc == '0') || (lc == '0' && rc == '1'))) {            return 0;        }        int count = 0;        while (l >= 0 && r < s.length() && lc == s.charAt(l) && rc == s.charAt(r)) {            count++;            l--;            r++;        }        return count;    }}

四、总结小记

• 2202/8/28 忽如一夜秋风至，吹落黄花满地金