线性动态规划：统计二进制子串中0和1数量相等的子串个数

题目描述
给定一个二进制字符串 s，只包含字符 '0' 和 '1'。统计并返回其中满足以下条件的非空子串的数目：子串中 '0' 和 '1' 的数量相等。
示例：
输入：s = "00110011"
输出：6
解释：满足条件的子串有："0011"（索引0-3）、"01"（索引1-2）、"1100"（索引2-5）、"10"（索引3-4）、"0011"（索引4-7）、"01"（索引5-6）。
注意：子串必须是连续的。

解题思路
这个问题可以看作一个“计数”问题，要求连续子串中0和1的数量相等。我们可以用“差值转换”的方法，将0视为-1，1视为+1，那么子串中0和1数量相等就等价于子串的和为0。问题转化为：在数组中统计和为零的连续子数组的个数。我们可以用线性动态规划（实际上是前缀和配合哈希表统计）在O(n)时间内解决。

详细步骤

步骤1：问题转换
将字符串s转换为整数数组arr，其中'0'对应-1，'1'对应+1。
例如：s = "00110011" → arr = [-1, -1, 1, 1, -1, -1, 1, 1]
此时，原问题等价于：在arr中统计和为0的连续子数组的个数。

步骤2：前缀和定义
定义前缀和prefix[i]为arr[0] + arr[1] + ... + arr[i-1]，prefix[0] = 0。
则子数组arr[i..j]的和 = prefix[j+1] - prefix[i]。
要求和为0，即prefix[j+1] - prefix[i] = 0 → prefix[j+1] = prefix[i]。
所以问题转化为：统计前缀和数组中，值相等的不同位置对(i, j)的个数，其中i < j。

步骤3：哈希表统计
遍历数组，计算当前前缀和sum，并用哈希表count记录每个前缀和值出现的次数。

• 初始化：count[0] = 1（前缀和为0在位置0出现一次）。
• 遍历每个字符c（索引从0开始）：
  • 如果c == '0'，sum += -1，否则sum += 1。
  • 检查当前sum是否在哈希表中出现过：如果出现过，那么当前sum与之前每个出现的位置都可以形成一个和为0的子数组。因此，新增的满足条件的子串个数 = count[sum]。
  • 将count[sum]加1，更新哈希表。
• 累加所有新增的子串个数，即为最终结果。

步骤4：举例推导
以s = "00110011"为例：

• 初始：sum=0, count={0:1}, result=0
• 索引0: '0' → sum=-1, count中没有-1，count={0:1, -1:1}, result=0
• 索引1: '0' → sum=-2, count中没有-2，count={0:1, -1:1, -2:1}, result=0
• 索引2: '1' → sum=-1, count[-1]=1，新增1个子串（"01"，索引1-2），result=1，count[-1]变为2
• 索引3: '1' → sum=0, count[0]=1，新增1个子串（"0011"，索引0-3），result=2，count[0]变为2
• 索引4: '0' → sum=-1, count[-1]=2，新增2个子串（"1100"，索引2-5 和 "10"，索引3-4），result=4，count[-1]变为3
• 索引5: '0' → sum=-2, count[-2]=1，新增1个子串（"0011"，索引4-7），result=5，count[-2]变为2
• 索引6: '1' → sum=-1, count[-1]=3，新增3个子串（"01"，索引5-6 和 其他两个更长的子串？这里需要仔细验证）。实际上，新增子串对应的起始位置是之前所有sum=-1的位置（索引0? 索引1? 索引4? 注意：sum=-1在索引2、索引4、索引6时都出现过，但起始位置是前缀和变化前的位置）。为了避免混淆，我们严格按照步骤计算：

实际过程（用前缀和数组更清晰）：
arr = [-1,-1,1,1,-1,-1,1,1]
前缀和prefix = [0,-1,-2,-1,0,-1,-2,-1,0]
找相等的前缀和：

• 0出现在索引0,4,8：对数为C(3,2)=3（子串索引0-3,4-7,0-7?注意最后一个0-7是全体，但全体0和1数量相等吗？这里全体4个0、4个1，是相等的，所以是有效的）。但题目例子输出是6，我们看看具体：
  相等前缀和对：
  (0,4) → 子串[0..3] "0011"
  (0,8) → 子串[0..7] "00110011"（全体）
  (4,8) → 子串[4..7] "0011"
  还有(-1,-1)对：
  (-1)出现在索引1,3,5,7：C(4,2)=6对，但注意这些对对应的子串是：
  (1,3) → 子串[1..2] "01"
  (1,5) → 子串[1..4] "0110"? 这个0和1个数：2个0、3个1？不对，检查：索引1-4: 0,1,1,0 → 0有2个，1有2个，确实相等。
  (1,7) → 子串[1..6] "011001"：0有3个，1有3个，相等。
  (3,5) → 子串[3..4] "10"
  (3,7) → 子串[3..6] "1001"：0有2个，1有2个，相等。
  (5,7) → 子串[5..6] "01"
  还有(-2,-2)对：出现在索引2,6 → 1对，子串[2..5] "1100"。
  总计：3+6+1=10？但示例输出是6，哪里出问题了？

我们发现，示例输出只统计了长度大于等于2的子串，但题目要求是“非空子串”，并没有排除全体。然而示例中全体"00110011"（索引0-7）并没有被计入输出6中。检查示例解释，它确实没包括全体。为什么？因为全体虽然0和1个数相等，但示例解释中没列出，可能它只列了部分？但题目要求统计所有。我们验证：s="00110011"，0的个数=4，1的个数=4，全体满足条件，应计数。但示例输出是6，说明全体不算？我们再检查示例中的子串：
"0011"（0-3）
"01"（1-2）
"1100"（2-5）
"10"（3-4）
"0011"（4-7）
"01"（5-6）
确实是6个，没有全体。
为什么全体不算？因为全体的长度是8，0和1个数相等，应该算。但示例没算，可能题目有隐藏条件：子串必须满足“0和1分别连续”？不对，看"1100"中0和1分别连续吗？"1100"中1连续、0连续，但"0011"也是连续。似乎这些子串都是“连续相同字符组成的块”的拼接。实际上，这个问题有一个更简单的解法：统计相邻的连续0和连续1的块，然后每对相邻块能形成的满足条件的子串个数是min(cnt0, cnt1)。用这个规则可得到示例6。

原来如此！我明白了，常见的“统计二进制子串”问题（LeetCode 696）的定义是：子串中所有0和所有1都是连续出现的，即子串是“连续相同字符块”组成的。但题目描述中并没有明确说明这一点，不过从示例可推断是这个意思。所以我们重新审题：统计具有相同数量的连续0和连续1组成的子串，即子串的形式是像“000111”或“1100”这样，前半段全是0、后半段全是1，或前半段全是1、后半段全是0，并且0和1的数量相等。

步骤5：修正问题
实际上，这是LeetCode 696题“计数二进制子串”的准确描述：计算具有相同数量连续0和连续1的子串数量。
例如："0011"包括子串"0011"、"01"、"1100"、"10"、"0011"、"01"，共6个。注意"00110011"全体不是这种形式，因为它有4段交替。

步骤6：动态规划思路
我们可以用线性动态规划，定义两个数组：

• zeros[i]：以i结尾的连续0的个数（如果s[i]是'0'）
• ones[i]：以i结尾的连续1的个数（如果s[i]是'1'）
  然后遍历每个位置i，如果s[i] != s[i-1]，则当前字符是新的连续段的开始，此时不能形成满足条件的子串（因为当前段长度=1，前一段长度已知）。我们可以在每次字符变化时，累加前一段和当前段中较短的长度，即为新增的满足条件的子串数。
  更简洁的方法：不显式用DP数组，而用两个变量prev和curr分别记录前一段连续长度和当前连续长度。

步骤7：算法步骤

1. 初始化：prev=0, curr=1, result=0
2. 从i=1遍历到n-1：
   • 如果s[i] == s[i-1]，curr++
   • 否则（字符变化），result += min(prev, curr)，然后prev=curr, curr=1
3. 最后再加上一次：result += min(prev, curr)
4. 返回result

注意：在第一次字符变化之前，prev=0，所以不会增加计数。
例如"00110011"：
i=1: '0'==prev → curr=2
i=2: '1'!='0' → result+=min(0,2)=0, prev=2, curr=1
i=3: '1'==prev → curr=2
i=4: '0'!='1' → result+=min(2,2)=2, prev=2, curr=1
i=5: '0'==prev → curr=2
i=6: '1'!='0' → result+=min(2,2)=4, prev=2, curr=1
i=7: '1'==prev → curr=2
遍历结束，result+=min(2,2)=6

步骤8：复杂度分析
时间复杂度：O(n)，一次遍历。
空间复杂度：O(1)，只用了常数变量。

最终代码（Python示例）

def countBinarySubstrings(s: str) -> int:
    n = len(s)
    prev, curr = 0, 1
    ans = 0
    for i in range(1, n):
        if s[i] == s[i-1]:
            curr += 1
        else:
            ans += min(prev, curr)
            prev, curr = curr, 1
    ans += min(prev, curr)
    return ans

这样，我们就用线性动态规划思想（实际是双指针/分组统计）解决了这个“统计二进制子串”问题。