What is the main pattern used to solve Count Substrings That Satisfy K-Constraint I?

The problem primarily uses a sliding window with running state updates to efficiently count valid substrings.

Can brute force solve this problem within constraints?

Yes, because the string length is up to 50, but sliding window is more efficient and avoids repeated computation.

How do you update state when the window slides?

Track consecutive 0s and 1s dynamically, incrementing or decrementing counts as characters enter or leave the window.

What happens if k equals the string length?

All substrings automatically satisfy the k-constraint, simplifying the counting to total substrings.

Are there common mistakes when implementing this sliding window?

Yes, such as miscounting overlapping substrings, forgetting to update consecutive counts, or off-by-one errors in the window boundaries.

#3258

Easy

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

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

给你一个二进制字符串 s 和一个整数 k 。如果一个二进制字符串满足以下任一条件，则认为该字符串满足 k 约束：字符串中 0 的数量最多为 k 。字符串中 1 的数量最多为 k 。返回一个整数，表示 s 的所有满足 k 约束的子字符串的数量。示例 1：输入： s = "1…

字符串滑动窗口

题目描述

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

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

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

返回一个整数，表示 s 的所有满足 k 约束 的子字符串的数量。

示例 1：

输入：s = "10101", k = 1

输出：12

解释：

s 的所有子字符串中，除了 "1010"、"10101" 和 "0101" 外，其余子字符串都满足 k 约束。

示例 2：

输入：s = "1010101", k = 2

输出：25

解释：

s 的所有子字符串中，除了长度大于 5 的子字符串外，其余子字符串都满足 k 约束。

示例 3：

输入：s = "11111", k = 1

输出：15

解释：

s 的所有子字符串都满足 k 约束。

提示：

1 <= s.length <= 50
1 <= k <= s.length
s[i] 是 '0' 或 '1'。

lightbulb

解题思路

方法一：滑动窗口

我们用两个变量 $\textit{cnt0}$ 和 $\textit{cnt1}$ 分别记录当前窗口内的 $0$ 和 $1$ 的个数，用 $\textit{ans}$ 记录满足 $k$ 约束的子字符串的个数，用 $l$ 记录窗口的左边界。

当我们右移窗口时，如果窗口内的 $0$ 和 $1$ 的个数都大于 $k$ ，我们就需要左移窗口，直到窗口内的 $0$ 和 $1$ 的个数都不大于 $k$ 。此时，窗口内所有以 $r$ 作为右端点的子字符串都满足 $k$ 约束，个数为 $r - l + 1$ ，其中 $r$ 是窗口的右边界。我们将这个个数累加到 $\textit{ans}$ 中。

最后，我们返回 $\textit{ans}$ 即可。

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

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int) -> int:
        cnt = [0, 0]
        ans = l = 0
        for r, x in enumerate(map(int, s)):
            cnt[x] += 1
            while cnt[0] > k and cnt[1] > k:
                cnt[int(s[l])] -= 1
                l += 1
            ans += r - l + 1
        return ans

speed

复杂度分析

指标	值
时间	complexity ranges from O(n^2) for brute force to O(n) for optimized sliding window with running state updates. Space complexity is O(1) for counters or O(n) if storing all valid substrings.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you notice a pattern where counting substrings can be done without full recomputation?
question_mark
Can you maintain a dynamic state as you expand the substring window?
question_mark
Consider what happens when k is equal to the length of s or 1.

warning

常见陷阱

外企场景

error
Failing to update counts correctly when the window slides, leading to double-counting.
error
Using brute force on longer strings can exceed time limits even though constraints are small.
error
Misinterpreting the k-constraint for consecutive 0s or 1s.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count substrings where the number of 1s minus 0s does not exceed k.
arrow_right_alt
Find the longest substring satisfying the k-constraint instead of counting all.
arrow_right_alt
Apply the k-constraint to ternary strings instead of binary strings.

help

常见问题

外企场景

继续练习

#3261 统计满足 K 约束的子字符串数量 II #3234 统计 1 显著的字符串的数量 #3297 统计重新排列后包含另一个字符串的子字符串数目 I