线性动态规划：统计二进制字符串中由相同数量的0和1组成的连续子串个数

题目描述
给定一个二进制字符串 s，其中只包含字符 '0' 和 '1'。请统计并返回其中由相同数量的0和1组成的连续子串的个数。
注意：子串必须是连续的，并且0和1的数量相等。
示例：
输入：s = "00110011"
输出：6
解释：有6个子串满足条件："0011"（位置0-3）、"01"（位置1-2）、"1100"（位置2-5）、"10"（位置3-4）、"0011"（位置4-7）、"01"（位置5-6）。
注意："00110011"本身并不是一个满足条件的子串，因为它包含4个0和4个1，但题目要求统计的是所有可能的连续子串。

解题思路
这是一个典型的线性动态规划问题，可以通过记录“差值”状态来巧妙解决。
核心思路：将字符 '0' 视为 -1，'1' 视为 +1（或反过来），这样“0和1数量相等”就转化为“子数组和为0”。但直接求和为0的子数组个数比较困难，我们采用“计数差值”的方法。

步骤详解

步骤1：问题转化
定义变量 count 记录当前扫描位置之前，1 的数量减去 0 的数量的差值（即“差值”）。
初始时，在字符串开始前，1 和 0 的数量都为0，差值 = 0。
关键观察：
假设在位置 i 和 j（i < j）处，差值相同，那么子串 s[i+1:j] 中 1 和 0 的数量相等。为什么？
因为差值表示从开头到当前位置的 1 的数量减去 0 的数量。如果两个位置的差值相同，说明从开头到这两个位置，1 比 0 多出的数量是相同的，那么这两个位置之间的部分，1 和 0 的增加量就相等，即子串中 1 和 0 的数量相等。

步骤2：状态定义
我们用一个哈希表（字典） mp 来记录每个差值出现的次数。
mp[diff] = k 表示在扫描过程中，差值 diff 出现了 k 次（包括初始状态）。
初始状态：mp[0] = 1，表示在开始前，差值为0出现了1次。

步骤3：遍历与累加
从左到右遍历字符串的每个字符：

• 遇到 '1'，差值加1。
• 遇到 '0'，差值减1。
  在当前位置，差值变为 curr 后，我们查看之前这个差值出现过几次。
  假设之前差值 curr 出现过 k 次，那么当前位置可以和之前每一个出现该差值的位置形成一个符合条件的子串，因此答案增加 k。
  然后更新哈希表，将差值 curr 的出现次数加1。

步骤4：举例说明
以 s = "00110011" 为例，逐步模拟：

初始化：mp = {0:1}, curr = 0, ans = 0

1. 字符 '0'：curr = 0 - 1 = -1
   mp 中没有 -1，所以 ans 不变。
   更新 mp：mp[-1] = 1

2. 字符 '0'：curr = -1 - 1 = -2
   mp 中没有 -2，ans 不变。
   mp[-2] = 1

3. 字符 '1'：curr = -2 + 1 = -1
   mp[-1] = 1，说明之前有一个位置（步骤1结束时）差值也是 -1，它们之间的子串（s[1:2] 即 "01"）满足条件，ans += 1 → ans=1。
   更新 mp：mp[-1] = 2

4. 字符 '1'：curr = -1 + 1 = 0
   mp[0] = 1，说明从开始到当前位置，差值重新变为0，子串 s[0:3] 即 "0011" 满足条件，ans += 1 → ans=2。
   mp[0] = 2

5. 字符 '0'：curr = 0 - 1 = -1
   mp[-1] = 2，说明之前有两个位置差值也是 -1（步骤1和步骤3），对应子串 s[1:4]? 需要仔细：
   步骤1结束时（位置0后）差值为-1，当前位置是4，子串 s[1:4] 是 "011"？不对，注意索引范围。
   更准确：当前位置索引为4（第五个字符），之前差值-1出现的位置索引分别是0和2（步骤1和步骤3结束后的位置）。

   • 与索引0之间：子串 s[1:4] 即 "011"（0和1数量：1个0，2个1）不相等？等下，我们检查：
     从索引1到4（包含索引1,2,3）是 "011"，0的数量1，1的数量2，不相等。
     这里发现一个关键点：差值记录的是从开头到当前位置结束的累积差值，所以两个位置 i 和 j 之间的子串是 s[i+1:j]（左开右闭）。
     所以：
   • 与索引0：子串 s[1:4] 是 "011"（索引1~3），0的数量1，1的数量2，不相等。
     这说明我们之前解释有误。让我们重新推导。

重新严谨推导
设 diff[i] 表示从 s[0] 到 s[i] 的累积和（'1'=+1, '0'=-1）。
如果 diff[i] = diff[j]（i < j），那么从 i+1 到 j 的子串的累积和为0，即这个子串中 '+1' 和 '-1' 数量相等。
因为 diff[j] - diff[i] = 0 就是子串 s[i+1:j] 的和。
所以条件成立。
那么在我们的遍历中，curr 就是当前的 diff 值。
在步骤5中，当前位置索引4（第五个字符 '0'），此时 curr = -1。
之前 curr = -1 出现在哪些位置？

• 第一次：索引0之后（字符 '0' 后），diff[0] = -1。
  子串 s[1:4] 是索引1,2,3 -> "011"，和 = +1+1-1? 重新计算："0"→-1, "1"→+1, "1"→+1，和 = (-1)+(+1)+(+1)=+1，不为0，所以不符合。
  咦，这说明我们记录的位置是字符之后，但 diff 是包含该字符的。
  设字符串索引从0开始，s="00110011"
  步骤记录：
  初始: diff=0
  索引0:'0' → diff=-1
  索引1:'0' → diff=-2
  索引2:'1' → diff=-1
  索引3:'1' → diff=0
  索引4:'0' → diff=-1

  现在索引4，diff=-1。之前 diff=-1 出现在索引0和索引2。
  对于索引0：子串索引1~4（即s[1:4]）是"011"? 索引1~4包含索引1,2,3,4? 不对，子串应该是 i+1 到 j，即从索引1到索引4（包含1,2,3,4）四个字符？这显然不对，因为原意是子串 s[i+1:j] 包含字符 i+1,...,j，长度 j-i。
  实际上，如果 diff[i] = diff[j]，子串 s[i+1..j] 的和为0。
  索引0: i=0, j=4, 子串 s[1..4] 是索引1,2,3,4 -> "0110"，和=(-1)+(+1)+(+1)+(-1)=0，对！
  所以 s[1..4] 是 "0110"，0的数量2，1的数量2，满足。
  这就是一个有效子串。
  对于索引2: i=2, j=4, 子串 s[3..4] 是 "10"，和=(+1)+(-1)=0，对。
  所以步骤5中，ans 应该增加2。

继续模拟：

初始化：mp={0:1}, curr=0, ans=0
i=0, s[0]='0', curr=-1, mp中没有-1，ans不变，mp[-1]=1
i=1, s[1]='0', curr=-2, mp中没有-2，ans不变，mp[-2]=1
i=2, s[2]='1', curr=-1, mp[-1]=1，ans+=1 → ans=1，mp[-1]=2
i=3, s[3]='1', curr=0, mp[0]=1，ans+=1 → ans=2，mp[0]=2
i=4, s[4]='0', curr=-1, mp[-1]=2，ans+=2 → ans=4，mp[-1]=3
i=5, s[5]='0', curr=-2, mp[-2]=1，ans+=1 → ans=5，mp[-2]=2
i=6, s[6]='1', curr=-1, mp[-1]=3，ans+=3 → ans=8，mp[-1]=4
i=7, s[7]='1', curr=0, mp[0]=2，ans+=2 → ans=10

得到 ans=10，但题目示例输出是6，哪里不对？
哦！题目要求是“由相同数量的0和1组成的连续子串”，注意示例中 "00110011" 输出6，而我们得到了10。
检查示例中的子串：
"0011"（位置0-3）
"01"（位置1-2）
"1100"（位置2-5）
"10"（位置3-4）
"0011"（位置4-7）
"01"（位置5-6）
确实只有6个。
我们的方法统计了所有和为0的子串，但示例中 "0110"（位置1-4）也是0和1数量相等（2个0，2个1），为什么不算？
原来示例中 "0110" 没有列出来，但按照题目描述，它应该是符合条件的。让我们验证题目描述：题目说“统计并返回其中由相同数量的0和1组成的连续子串的个数”，那么 "0110" 应该被计入。
但示例输出是6，可能示例解释漏了？我们验证字符串 "00110011" 的所有满足条件的子串：
列出所有连续子串并检查0和1数量相等：
长度2: "00"(0,2), "01"(1,1), "11"(2,2), "10"(1,1), "00"(2,0), "01"(1,1), "11"(2,2) → 符合条件的："01"（索引1-2），"10"（3-4），"01"（5-6） → 3个
长度4: "0011"(2,2), "0110"(2,2), "1100"(2,2), "1001"(2,2), "0011"(2,2) → 符合条件的：全部5个？数一下：
"0011"索引0-3: 2个0,2个1 ✓
"0110"索引1-4: 2个0,2个1 ✓
"1100"索引2-5: 2个1,2个0 ✓
"1001"索引3-6: 2个0,2个1 ✓
"0011"索引4-7: 2个0,2个1 ✓
所以长度4有5个。
长度6: "001100"(3,3), "011001"(3,3), "110011"(3,3) → 都符合？0和1数量都是3？是的，每个都是3个0和3个1，所以3个。
长度8: "00110011"(4,4) → 符合。
总数 = 3+5+3+1 = 12，但我们的方法得到10，示例说是6，明显不一致。
等等，我明白了！题目中的示例 "00110011" 输出6，可能是指“由相同数量的0和1组成，且0和1是连续分组出现的”？不，题目没有这么说。
查阅原题（LeetCode 696. Count Binary Substrings），题目要求的是“具有相同数量0和1，且0和1都是连续出现的子串”。
这才是关键！题目要求子串中所有的0和所有的1都是连续出现的，比如 "0011" 中0连续，1连续；但 "0101" 不符合，因为0和1交替出现。
所以我们的方法需要调整。

步骤5：调整思路
原题是 LeetCode 696. Count Binary Substrings。
条件：子串中0和1的数量相等，且0和1都是连续分组出现的。
例如 "0011" 符合，"0101" 不符合。
那么我们可以用“分组”的思想。
将字符串按连续相同字符分组，记录每组的长度。
比如 "00110011" 分组为：2个0, 2个1, 2个0, 2个1 → 长度数组 [2,2,2,2]
然后统计相邻两个分组的最小值之和。
为什么？
考虑相邻两组，比如一组0长度为2，一组1长度为2，那么它们可以形成的满足条件的子串数量为 min(2,2)=2，即："0011" 和 "01"（从第一组取1个0和1个1，或取2个0和2个1）。
更一般地，对于相邻两组长度分别为 a 和 b，它们可以形成 min(a,b) 个符合条件的子串，这些子串分别从两组中各取1,2,...,min(a,b) 个字符，并且保持连续性。
所以算法：

1. 遍历字符串，记录当前连续字符的长度。
2. 遇到字符变化时，将前一个连续段的长度记录下来。
3. 每得到一个新的连续段长度 curr_len，它与前一个连续段长度 prev_len 可以形成 min(prev_len, curr_len) 个有效子串，累加到答案。
4. 更新 prev_len = curr_len，继续。

步骤6：重新模拟示例
s = "00110011"
分组长度：

• 开始字符 '0'，连续2个0 → curr_len=2，prev_len=0，ans += min(0,2)=0
• 变为 '1'，连续2个1 → prev_len=2, curr_len=2, ans += min(2,2)=2
• 变为 '0'，连续2个0 → prev_len=2, curr_len=2, ans += min(2,2)=4
• 变为 '1'，连续2个1 → prev_len=2, curr_len=2, ans += min(2,2)=6
  结束，ans=6，符合示例。

步骤7：算法总结

1. 初始化 ans = 0, prev_len = 0, curr_len = 1（从第一个字符开始计数）。
2. 从第二个字符开始遍历字符串：
   • 如果当前字符等于前一个字符，curr_len += 1。
   • 如果不相等，则遇到新分组：
     ans += min(prev_len, curr_len)
     prev_len = curr_len
     curr_len = 1（新分组长度为1）
3. 遍历结束后，还要处理最后一组：ans += min(prev_len, curr_len)
4. 返回 ans。

时间复杂度 O(n)，空间复杂度 O(1)。

步骤8：代码实现（Python）

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

步骤9：验证
输入 "00110011"，输出6。
输入 "10101"，分组：1个1,1个0,1个1,1个0,1个1 → 相邻最小值依次为0,1,1,1,0，和为3，即 "10", "01", "10", "01" 四个？等等，分组长度数组 [1,1,1,1,1]
计算：
prev_len=0, curr_len=1 → ans+=0
遇到变化：prev_len=1, curr_len=1 → ans+=1
遇到变化：prev_len=1, curr_len=1 → ans+=2
遇到变化：prev_len=1, curr_len=1 → ans+=3
最后 ans+=min(1,1)=4
有效子串："10", "01", "10", "01" 共4个，符合预期。

总结
本题通过分组统计，利用相邻分组的最小值来计数满足条件的子串个数，是一个巧妙的线性动态规划思想。关键点是理解条件“0和1连续出现”转化为分组长度比较。