【LetMeFly】696.计数二进制子串：一次遍历
力扣题目链接：https://leetcode.cn/problems/count-binary-substrings/
给定一个字符串 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 <= 105s[i] 为 '0' 或 '1'
解题方法：遍历
3个连续的1紧接着2个连续的0一共可以组成2个等01连续子串（11100的等01连续子串有1100和10），因此我们只需要一次遍历，将字符串变成“连续两个1、连续3个0、连续5个1、…”这种就行了。
- 时间复杂度$O(len(s))$
- 空间复杂度$O(1)$
AC代码
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
int countBinarySubstrings(string s) {
int ans = 0;
for (int i = 1, n = s.size(), cnt = 1, lastCnt = 0; i <= n; i++, cnt++) {
if (i == n || s[i] != s[i - 1]) {
ans += min(cnt, lastCnt);
lastCnt = cnt;
cnt = 0;
}
}
return ans;
}
};
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| '''
LastEditTime: 2026-02-19 11:33:22
'''
class Solution:
def countBinarySubstrings(self, s: str) -> int:
ans = lastCnt = 0
cnt = 1
for i in range(1, len(s) + 1):
if i == len(s) or s[i] != s[i - 1]:
ans += min(lastCnt, cnt)
lastCnt = cnt
cnt = 0
cnt += 1
return ans
|
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public int countBinarySubstrings(String s) {
int ans = 0;
for (int i = 1, n = s.length(), cnt = 1, lastCnt = 0; i <= n; i++) {
if (i == n || s.charAt(i) != s.charAt(i - 1)) {
ans += Math.min(cnt, lastCnt);
lastCnt = cnt;
cnt = 0;
}
cnt++;
}
return ans;
}
}
|
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
package main
func countBinarySubstrings(s string) (ans int) {
lastCnt, cnt := 0, 1
for i := 1; i <= len(s); i++ {
if i == len(s) || s[i] != s[i - 1] {
ans += min(lastCnt, cnt);
lastCnt = cnt;
cnt = 0;
}
cnt++;
}
return;
}
|
Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
impl Solution {
pub fn count_binary_substrings(s: String) -> i32 {
let s = s.as_bytes();
let mut ans = 0;
let mut cnt = 1;
let mut last_cnt = 0;
for i in 1..(s.len() + 1) {
if i == s.len() || s[i] != s[i - 1] {
ans += cnt.min(last_cnt);
last_cnt = cnt;
cnt = 0;
}
cnt += 1;
}
ans
}
}
|
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源