题目

题目来源：力扣（LeetCode）

给定一个字符串 s，计算具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 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。

思路分析

按字符分组

  1. 将字符串 s 按照 00和 1 的连续段分组，存在 counts 数组中，例如 s = 00111011，可以得到这样的 counts 数组：count=[2, 3, 1, 2]。

  2. 这里 counts 数组中两个相邻的数一定代表的是两种不同的字符。假设 counts 数组中两个相邻的数字为 u 或者 v，它们对应着 u 个 和 vv 个 1，或者 u 个 1 和 v 个 0。它们能组成的满足条件的子串数目为 min(u, v)，即一对相邻的数字对答案的贡献。

  3. 我们只要遍历所有相邻的数对，求它们的贡献总和，即可得到答案。

  1. /**
  2.  * @param {string} s
  3.  * @return {number}
  4.  */
  5. var countBinarySubstrings = function (s) {
  6.   const counts = [];
  7.   let ptr = 0, n = s.length;
  8.   // 按照 0 和 1 的连续段分组，存在 counts 数组中
  9.   while (ptr < n) {
  10.     const c = s.charAt(ptr);
  11.     let count = 0;
  12.     while (ptr < n && s.charAt(ptr) === c) {
  13.       ++ptr;
  14.       ++count;
  15.     }
  16.     counts.push(count);
  17.   }
  18.   let ans = 0;
  19.   // counts 数组中两个相邻数字的 Math.min(counts[i], counts[i - 1]) 为满足条件的子串数目
  20.   // 遍历所有相邻的数对，求它们的总和
  21.   for (let i = 1; i < counts.length; ++i) {
  22.     ans += Math.min(counts[i], counts[i - 1]);
  23.   }
  24.   return ans;
  25. };