How do I approach the 'Count Binary Substrings' problem?

Start by using the two-pointer scanning approach to identify consecutive 1's and 0's, then group them to count valid substrings.

What is the primary pattern used in 'Count Binary Substrings'?

The key pattern is two-pointer scanning with invariant tracking of consecutive groups of 1's and 0's.

How can I optimize space while solving 'Count Binary Substrings'?

Keep track of the previous segment's length without using extra data structures. This ensures O(1) space complexity.

What is the time complexity of 'Count Binary Substrings'?

The time complexity is O(N), where N is the length of the binary string, because the solution processes the string in one pass.

Are there any edge cases to consider for 'Count Binary Substrings'?

Yes, ensure to handle cases with strings where 0's and 1's alternate, or when one digit significantly exceeds the other in length.

#696

Easy

auto_awesome双·指针·invariant

LeetCode 题解工作台

计数二进制子串

给定一个字符串 s ，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组连续的。重复出现（不同位置）的子串也要统计它们出现的次数。示例 1：输入： s = "00110011" 输出： 6 解释： 6 个子串满足具有相同数量的连…

双指针字符串

题目描述

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

lightbulb

解题思路

方法一：遍历计数

我们可以遍历字符串 $s$ ，用一个变量 $\textit{pre}$ 记录上一个连续字符的数量，另一个变量 $\textit{cur}$ 记录当前连续字符的数量。那么以当前字符结尾的满足条件的子串数量为 $\min(\textit{pre}, \textit{cur})$ 。我们将 $\min(\textit{pre}, \textit{cur})$ 累加到答案中，并将 $\textit{cur}$ 的值赋给 $\textit{pre}$ ，继续遍历字符串 $s$ 直到结束。

时间复杂度 $O(n)$ ，其中 $n$ 是字符串 $s$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        n = len(s)
        ans = i = 0
        pre = 0
        while i < n:
            j = i + 1
            while j < n and s[j] == s[i]:
                j += 1
            cur = j - i
            ans += min(pre, cur)
            pre = cur
            i = j
        return ans

speed

复杂度分析

指标	值
时间	O(N)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Look for an understanding of how to manage multiple groups of consecutive 1's and 0's efficiently.
question_mark
Evaluate if the candidate can explain the trade-offs between time complexity and space optimization in this problem.
question_mark
Check for the ability to reason about how to handle substrings that repeat in the final count.

warning

常见陷阱

外企场景

error
Failing to handle repeated substrings correctly – the solution should count each occurrence of valid substrings.
error
Incorrectly grouping consecutive characters, which may lead to missing valid substrings.
error
Not optimizing space by avoiding unnecessary data structures – the two-pointer approach should be used with careful tracking.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider if the input string includes alternating characters, like "010101".
arrow_right_alt
What happens if the binary string has segments where the count of 0's or 1's exceeds the count of the other?
arrow_right_alt
How would the solution adapt if we are asked to find the longest valid substring instead of counting them?

help

常见问题

外企场景

继续练习

#680 验证回文串 II #647 回文子串 #763 划分字母区间