来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-binary-substrings/

描述

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

注意：
s.length 在1到50,000之间。
s 只包含“0”或“1”字符。

题解

按字符分组

  • 剥离现象，看本质。符合条件的均由10\01扩展，如1100、111000、0011；
  • 将字符分组。11000111000000，可分组为groups[0] = 2，groups[1] = 3，groups[2] = 3，groups[3] = 6；
  • 取min(groups[i-1], groups[i])的和；
  1. class Solution {
  2.     public int countBinarySubstrings(String s) {
  3.         int[] groups = new int[s.length()];
  4.         int t = 0;
  5.         groups[0] = 1;
  6.         for (int i = 1; i < s.length(); i++) {
  7.             if (s.charAt(i - 1) != s.charAt(i)) {
  8.                 groups[++t] = 1;
  9.             } else {
  10.                 groups[t]++;
  11.             }
  12.         }
  14.         int ans = 0;
  15.         for (int i = 1; i <= t; i++) ans += Math.min(groups[i - 1], groups[i]);
  16.         return ans;
  17.     }
  18. }

复杂度分析

  • 时间度分析：O(N)；
  • 空间复杂度：O(N)，groups使用的空间；

    线性扫描

    优化空间复杂度，实时计算答案。
  1. class Solution {
  2.     public int countBinarySubstrings(String s) {
  3.         int prev = 0, cur = 1, ans = 0;
  4.         for (int i = 1; i < s.length(); i++) {
  5.             if (s.charAt(i) != s.charAt(i - 1)) {
  6.                 ans += Math.min(cur, prev);
  7.                 prev = cur;
  8.                 cur = 1; 
  9.             } else {
  10.                 cur++;
  11.             }
  12.         }
  13.         return ans + Math.min(cur, prev);
  14.     }
  15. }

复杂度分析

  • 时间度分析：O(N)；
  • 空间复杂度：O(1)；