给定一个字符串 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。

题解

如题目所示，子串必须包含“0”和“1”，且数量相等

假设输入“00111100011”，想要获得所有满足条件的子串，可以将输入字符串划分为包含连续0和1的字符串 “001111” “111000” “00011”

“001111”中，可以得到“01” “0011”，2个满足条件的子串，因为“0”最多才2个
“111000”中，可以得到“10” “1100” “111000”，3个满足条件的子串
“00011”中，可以得到“01”“0011”，2个满足条件的子串，因为“1”最多才2个

由此可以发现分割后的字符中满足条件的子串数量为“0”或“1”中个数少那个

“00111100011” 由 2个0 + 4个1 + 3个0 + 2个1 组成，记做 [2, 4, 3, 2]

再两两相比较，取小值累加的合，即 2 + 3 + 2 = 7

  1. /**
  2.  * @param {string} s
  3.  * @return {number}
  4.  */
  5. var countBinarySubstrings = function(s) {
  6.     const arr = []
  7.     let cur = s[0]
  8.     let n = 1
  9.     for (let i = 1; i < s.length; i++) {
  10.         if (s[i] === cur) {
  11.             n++
  12.         } else {
  13.             arr.push(n)
  14.             n = 1
  15.             cur = s[i]
  16.         }
  17.     }
  18.     arr.push(n)
  19.     let res = 0
  20.     for (let i = 0; i < arr.length - 1; i++) {
  21.         res += Math.min(arr[i], arr[i + 1])
  22.     }
  23.     return res
  24. };

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