696. 计数二进制子串

🟢   🔖  双指针 字符串  🔗 力扣 LeetCode

题目

Given a binary string s, return the number of non-empty substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: s = "00110011"

Output: 6

Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".

Notice that some of these substrings repeat and are counted the number of times they occur.

Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

Example 2:

Input: s = "10101"

Output: 4

Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

Constraints:

• 1 <= s.length <= 10^5
• s[i] is either '0' or '1'.

题目大意

给定一个字符串 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 <= 10^5
• s[i] 为 '0' 或 '1'

解题思路

为了满足条件，可以发现：

1. 字符串中每一组连续的 0 和 1 是互相分隔的，可以按连续的 0 和 1 分组。 例如，对于 s = "001110011", 可分为：[2, 3, 2, 2]，表示连续出现的 0 和 1 的数量。
2. 任意两个相邻的分组中，能形成的符合条件的子串数量，等于这两个分组中较小的那个组的数量。
   • 例如分组为 [2, 3]，能形成的子串为 min(2, 3) = 2。
3. 最终只需累加所有相邻分组的最小值即可。

---

思路一：分组数组

1. 初始化分组数组:

   • 定义一个数组 group，用来存储字符串中每一组连续字符的数量。例如，对于字符串 s = "00110"，group 最终会变成 [2, 2, 1]。
   • 初始值为 group = [1]，表示第一个字符（s[0]）的数量是 1。

2. 遍历字符串，进行分组统计:

   • 从第二个字符（s[1]）开始遍历，对比当前字符和前一个字符的值（s[i] == s[i - 1]）：
     • 如果相同，则将当前分组的数量加 1。
     • 如果不同，说明进入了新的一组，将新的一组数量初始化为 1 并加入 group。

3. 统计满足条件的子串数量:

   • 遍历 group 中的相邻分组（从第二组开始）
   • 任意两个相邻分组能形成的子串数量是它们之间的最小值
   • 累加这些最小值，即为满足条件的子串总数。

4. 返回结果:

   • 最后返回累加的子串数量 res。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。
  • 遍历字符串时，构造分组数组需要 O(n)。
  • 遍历分组数组时，统计子串数量需要 O(k)，其中 k 是分组的数量。
  • 因为 k <= n，总复杂度为 O(n)。
• 空间复杂度：O(n)。
  • 显式构造了一个分组数组 group，空间复杂度为 O(k)，其中 k 是分组数量。
  • 在极端情况下（如 s = "010101"），分组数量 k = n/2，因此最坏情况下空间复杂度为 O(n)。

---

思路二：优化版

可以继续优化上述思路，省去显式的分组统计，采用两个变量 prev 和 cur 动态更新当前和上一个分组的长度。

1. 初始化变量:

   • prev = 0: 表示上一组的连续字符数量，初始为 0。
   • cur = 1: 表示当前组的连续字符数量，初始为 1（因为第一个字符本身是一组）。
   • res = 0: 用于累计符合条件的子串数量。

2. 遍历字符串:

   • 如果当前字符和前一个字符相同，则增加当前组的数量 cur++。
   • 如果不同，则：
     • 将上一组的长度 prev 更新为当前组的长度 cur。
     • 将当前组 cur 重置为 1（新字符开始新的分组）。
     • 累加 res，加上上一组和当前组中较小的那个值：res += Math.min(prev, cur)。

3. 收尾处理:

   • 遍历完成后，再加一次最后一组和倒数第二组的比较值：res += Math.min(prev, cur)。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度，遍历字符串一次。
• 空间复杂度：O(1)，优化版使用常数个变量。

代码

分组数组

/**
 * @param {string} s
 * @return {number}
 */
var countBinarySubstrings = function (s) {
	let group = [1];
	for (let i = 1; i < s.length; i++) {
		if (s[i - 1] == s[i]) {
			group[group.length - 1]++;
		} else {
			group.push(1);
		}
	}
	let res = 0;
	for (let i = 1; i < group.length; i++) {
		res += Math.min(group[i - 1], group[i]);
	}
	return res;
};

优化版

/**
 * @param {string} s
 * @return {number}
 */
var countBinarySubstrings = function (s) {
	let prev = 0,
		cur = 1;
	let res = 0;
	for (let i = 1; i < s.length; i++) {
		if (s[i - 1] == s[i]) {
			cur++;
		} else {
			res += Math.min(prev, cur);
			prev = cur;
			cur = 1;
		}
	}
	return (res += Math.min(prev, cur));
};

相关题目

题号	标题	题解	标签	难度	力扣
271	字符串的编码与解码 🔒		设计 数组 字符串	🟠	🀄️ 🔗
2489	固定比率的子字符串数 🔒		哈希表 数学 字符串 1+	🟠	🀄️ 🔗
3234	统计 1 显著的字符串的数量		字符串 枚举 滑动窗口	🟠	🀄️ 🔗