How can binary search be applied in Count Substrings That Satisfy K-Constraint II?

Binary search is used to find the maximum valid substring length that satisfies the k-constraint, optimizing the solution by narrowing down potential answers.

What is the sliding window approach used for?

The sliding window technique helps to efficiently count valid substrings by dynamically adjusting the window size and checking the constraint without redundant operations.

What role does prefix sum play in solving the problem?

Prefix sum is used to preprocess the binary string, allowing quick retrieval of valid substrings within a specific query range, thus improving efficiency.

What is the primary challenge in solving this problem?

The main challenge is efficiently answering multiple range queries on a large binary string, which requires preprocessing and optimizing with binary search or sliding window.

Can this problem be generalized to other constraints?

Yes, the problem can be adapted to handle different types of constraints, such as substring length or the occurrence of other characters beyond '0' and '1'.

#3261

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

统计满足 K 约束的子字符串数量 II

给你一个二进制字符串 s 和一个整数 k 。另给你一个二维整数数组 queries ，其中 queries[i] = [l i , r i ] 。如果一个二进制字符串满足以下任一条件，则认为该字符串满足 k 约束：字符串中 0 的数量最多为 k 。字符串中 1 的数量最多为 k 。…

数组字符串二分查找滑动窗口前缀和

题目描述

给你一个 二进制 字符串 s 和一个整数 k。

另给你一个二维整数数组 queries ，其中 queries[i] = [l_i, r_i] 。

如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：

字符串中 0 的数量最多为 k。
字符串中 1 的数量最多为 k。

返回一个整数数组 answer ，其中 answer[i] 表示 s[l_i..r_i] 中满足 k 约束 的子字符串的数量。

示例 1：

输入：s = "0001111", k = 2, queries = [[0,6]]

输出：[26]

解释：

对于查询 [0, 6]， s[0..6] = "0001111" 的所有子字符串中，除 s[0..5] = "000111" 和 s[0..6] = "0001111" 外，其余子字符串都满足 k 约束。

示例 2：

输入：s = "010101", k = 1, queries = [[0,5],[1,4],[2,3]]

输出：[15,9,3]

解释：

s 的所有子字符串中，长度大于 3 的子字符串都不满足 k 约束。

提示：

1 <= s.length <= 10⁵
s[i] 是 '0' 或 '1'
1 <= k <= s.length
1 <= queries.length <= 10⁵
queries[i] == [l_i, r_i]
0 <= l_i <= r_i < s.length
所有查询互不相同

lightbulb

解题思路

方法一：滑动窗口 + 前缀和

我们用两个变量 $\textit{cnt0}$ 和 $\textit{cnt1}$ 分别记录当前窗口内的 $0$ 和 $1$ 的个数，指针 $i$ 和 $j$ 分别标识窗口的左右边界。用一个数组 $d$ 记录每个位置 $i$ 右边第一个不满足 $k$ 约束的位置，初始时 $d[i] = n$ 。另外，用一个长度为 $n + 1$ 的前缀和数组 $\textit{pre}[i]$ 记录以前 $i$ 个位置作为右边界的满足 $k$ 约束的子字符串的个数。

当我们右移窗口时，如果窗口内的 $0$ 和 $1$ 的个数都大于 $k$ ，我们将 $d[i]$ 更新为 $j$ ，表示位置 $i$ 右边第一个不满足 $k$ 约束的位置。然后我们将 $i$ 右移一位，直到窗口内的 $0$ 和 $1$ 的个数都不大于 $k$ 。此时，我们可以计算出以 $j$ 为右边界的满足 $k$ 约束的子字符串的个数，即 $j - i + 1$ ，我们更新到前缀和数组中。

最后，对于每个查询 $[l, r]$ ，我们首先找出 $l$ 右边第一个不满足 $k$ 约束的位置 $p$ ，那么 $p = \min(r + 1, d[l])$ ，那么 $[l, p - 1]$ 的所有子字符串都满足 $k$ 约束，个数为 $(1 + p - l) \times (p - l) / 2$ ，然后，我们计算以 $[p, r]$ 为右边界的满足 $k$ 约束的子字符串的个数，即 $\textit{pre}[r + 1] - \textit{pre}[p]$ ，最后将两者相加即可。

时间复杂度 $O(n + m)$ ，空间复杂度 $O(n)$ 。其中 $n$ 和 $m$ 分别为字符串 $s$ 的长度和查询数组 $\textit{queries}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def countKConstraintSubstrings(
        self, s: str, k: int, queries: List[List[int]]
    ) -> List[int]:
        cnt = [0, 0]
        i, n = 0, len(s)
        d = [n] * n
        pre = [0] * (n + 1)
        for j, x in enumerate(map(int, s)):
            cnt[x] += 1
            while cnt[0] > k and cnt[1] > k:
                d[i] = j
                cnt[int(s[i])] -= 1
                i += 1
            pre[j + 1] = pre[j] + j - i + 1
        ans = []
        for l, r in queries:
            p = min(r + 1, d[l])
            a = (1 + p - l) * (p - l) // 2
            b = pre[r + 1] - pre[p]
            ans.append(a + b)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates understanding of sliding window and prefix sum techniques.
question_mark
Candidate approaches binary search over valid answer space for query optimization.
question_mark
Candidate focuses on reducing time complexity when processing large query sets.

warning

常见陷阱

外企场景

error
Failing to optimize the solution for large inputs, resulting in slow runtime.
error
Incorrectly managing query bounds or assuming substrings without proper validation.
error
Misunderstanding the k-constraint or binary search, leading to incorrect counting of valid substrings.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count substrings for other constraints, such as length or specific substring characters.
arrow_right_alt
Generalize the problem to non-binary strings or extended constraint conditions.
arrow_right_alt
Handle multiple queries simultaneously without preprocessing, testing for a less efficient solution.

help

常见问题

外企场景

继续练习

#3346 执行操作后元素的最高频率 I #3347 执行操作后元素的最高频率 II #3413 收集连续 K 个袋子可以获得的最多硬币数量