题目

难度：★★☆☆☆
类型：字符串

给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。

重复出现的子串要计算它们出现的次数。

注意
s.length 在1到50,000之间。
s 只包含“0”或“1”字符。

示例 1

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

示例 2
输入: "10101"
输出: 4
解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。

解答

我们使用一个长度为2的滑窗遍历整个字符串，如果窗口中的两个字符（s[i]与s[i+1]）不同，则以该长度为2的子串为基础向左右同步扩展，探测伸长的子串是否可以满足要求。期间，需要用变量即时统计满足要求的子串数目。

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        count = 0                                                       # 计数器
        for i in range(len(s)-1):                                      # 遍历
            left, right = s[i], s[i+1]                                  # 左右
            left_idx, right_idx = i, i+1                                # 左右探测器下标
            if left != right:                                           # 如果遇到不同，开始探测
                # 只要左右探测端满足下标要求，并且符合题目条件
                while 0 <= left_idx <= right_idx < len(s) and \
                      s[left_idx] == left and s[right_idx] == right:
                    count += 1                                          # 计数器+1
                    left_idx, right_idx = left_idx - 1, right_idx + 1   # 左右扩展探索范围
        return count

举例说明：

测试案例：“00001111”
下标i为0、1、2时，没有遇到s[i]!=s[i+1]的情况；

i = 3时，s[i]='0'，s[i+1]='1'，满足条件，此时子串为"01"，计数器+1，并开始左右扩展：

    i = 3，左右指针各扩展1个单位，满足s[i-1]=='0'，s[i+2]=='1'，此时子串为s[i-1:i+3]="0011"，计数器+1；

    i = 3，左右指针各扩展2个单位，满足s[i-2]=='0'，s[i+3]=='1'，此时子串为s[i-2:i+4]="000111"，满足条件，计数器+1；

    i = 3，左右指针各扩展3个单位，满足s[i-3]=='0'，s[i+4]=='1'，此时子串为s[i-3:i+5]=="00001111"，满足条件，计数器+1；

    i = 3，左右纸质各扩展4个单位，发现下标越界，结束本轮i=3的探测。

i等于4,5,6时，发现滑窗中两个元素都是1，不进行左右探测。

如有疑问或建议，欢迎评论区留言~