LeetCode 696. 计数二进制子串

Categories:

题目描述
思路分析
1. 解法一：分组计数（推荐）
相似题目

题目描述

✅ 696. 计数二进制子串

思路分析

解法一：分组计数（推荐）

核心思路：

把字符串按连续相同字符分组，得到每组长度。

相邻两组能形成的合法子串数为 min(prev, cur)。

累加所有相邻组的最小值即可。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(1)。

class Solution {
    public int countBinarySubstrings(String s) {
        int prev = 0;
        int cur = 1;
        int total = 0;

        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                cur++;
            } else {
                total += Math.min(prev, cur);
                prev = cur;
                cur = 1;
            }
        }

        total += Math.min(prev, cur);
        return total;
    }
}

func countBinarySubstrings(s string) int {
	prev := 0
	cur := 1
	total := 0

	for i := 1; i < len(s); i++ {
		if s[i] == s[i-1] {
			cur++
		} else {
			total += min(prev, cur)
			prev = cur
			cur = 1
		}
	}

	total += min(prev, cur)
	return total
}

func min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

相似题目

题目	难度	考察点
459. 重复的子字符串	简单	字符串
443. 压缩字符串	中等	分组统计
1004. 最大连续1的个数 III	中等	滑动窗口
485. 最大连续 1 的个数	简单	双指针
1668. 最大重复子字符串	简单	字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/32222565