Question

696. 计数二进制子串

English Version

题目描述

给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组连续的。

重复出现（不同位置）的子串也要统计它们出现的次数。

 

示例 1：

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

示例 2：

输入：s = "10101"
输出：4
解释：有 4 个子串："10"、"01"、"10"、"01" ，具有相同数量的连续 1 和 0 。

 

提示：

• 1 <= s.length <= 105
• s[i] 为 '0' 或 '1'

解法

方法一

class Solution:
  def countBinarySubstrings(self, s: str) -> int:
    i, n = 0, len(s)
    t = []
    while i < n:
      cnt = 1
      while i + 1 < n and s[i + 1] == s[i]:
        cnt += 1
        i += 1
      t.append(cnt)
      i += 1
    ans = 0
    for i in range(1, len(t)):
      ans += min(t[i - 1], t[i])
    return ans

class Solution {
  public int countBinarySubstrings(String s) {
    int i = 0, n = s.length();
    List<Integer> t = new ArrayList<>();
    while (i < n) {
      int cnt = 1;
      while (i + 1 < n && s.charAt(i + 1) == s.charAt(i)) {
        ++i;
        ++cnt;
      }
      t.add(cnt);
      ++i;
    }
    int ans = 0;
    for (i = 1; i < t.size(); ++i) {
      ans += Math.min(t.get(i - 1), t.get(i));
    }
    return ans;
  }
}

class Solution {
public:
  int countBinarySubstrings(string s) {
    int i = 0, n = s.size();
    vector<int> t;
    while (i < n) {
      int cnt = 1;
      while (i + 1 < n && s[i + 1] == s[i]) {
        ++cnt;
        ++i;
      }
      t.push_back(cnt);
      ++i;
    }
    int ans = 0;
    for (i = 1; i < t.size(); ++i) ans += min(t[i - 1], t[i]);
    return ans;
  }
};

func countBinarySubstrings(s string) int {
  i, n := 0, len(s)
  var t []int
  for i < n {
    cnt := 1
    for i+1 < n && s[i+1] == s[i] {
      i++
      cnt++
    }
    t = append(t, cnt)
    i++
  }
  ans := 0
  for i := 1; i < len(t); i++ {
    ans += min(t[i-1], t[i])
  }
  return ans
}