LeetCode 题解工作台
统计 1 显著的字符串的数量
给你一个二进制字符串 s 。 请你统计并返回其中 1 显著 的 子字符串 的数量。 如果字符串中 1 的数量 大于或等于 0 的数量的 平方 ，则认为该字符串是一个 1 显著 的字符串 。 示例 1： 输入： s = "00011" 输出： 5 解释： 1 显著的子字符串如下表所示。 i j s[i…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 滑动窗口（状态滚动更新）
答案摘要
根据题目描述，显著字符串满足 $\textit{cnt}_1 \geq \textit{cnt}_0^2$，那么 的最大值不超过 ，其中 是字符串的长度。因此我们可以枚举 的值，然后计算满足条件的子字符串数量。 我们首先预处理字符串中每个位置开始的第一个 的位置，存储在数组 中，其中 表示从位置 开始的第一个 的位置，如果不存在则为 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 滑动窗口（状态滚动更新） 题型思路
题目描述
给你一个二进制字符串 s。
请你统计并返回其中 1 显著 的 子字符串 的数量。
如果字符串中 1 的数量 大于或等于 0 的数量的 平方，则认为该字符串是一个 1 显著 的字符串 。
示例 1：
输入：s = "00011"
输出：5
解释：
1 显著的子字符串如下表所示。
| i | j | s[i..j] | 0 的数量 | 1 的数量 |
|---|---|---|---|---|
| 3 | 3 | 1 | 0 | 1 |
| 4 | 4 | 1 | 0 | 1 |
| 2 | 3 | 01 | 1 | 1 |
| 3 | 4 | 11 | 0 | 2 |
| 2 | 4 | 011 | 1 | 2 |
示例 2：
输入：s = "101101"
输出：16
解释：
1 不显著的子字符串如下表所示。
总共有 21 个子字符串，其中 5 个是 1 不显著字符串，因此有 16 个 1 显著子字符串。
| i | j | s[i..j] | 0 的数量 | 1 的数量 |
|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 |
| 4 | 4 | 0 | 1 | 0 |
| 1 | 4 | 0110 | 2 | 2 |
| 0 | 4 | 10110 | 2 | 3 |
| 1 | 5 | 01101 | 2 | 3 |
提示：
1 <= s.length <= 4 * 104s仅包含字符'0'和'1'。
解题思路
方法一：预处理 + 枚举
根据题目描述，显著字符串满足 ，那么 的最大值不超过 ，其中 是字符串的长度。因此我们可以枚举 的值，然后计算满足条件的子字符串数量。
我们首先预处理字符串中每个位置开始的第一个 的位置，存储在数组 中，其中 表示从位置 开始的第一个 的位置，如果不存在则为 。
接下来，我们遍历字符串的每个位置 作为子字符串的起始位置，初始化 的值为 或 （取决于当前位置是否为 ）。然后我们使用一个指针 从位置 开始，逐步跳转到下一个 的位置，同时更新 的值。
对于从位置 开始，且包含 个 的子字符串，最多可以包含 个 。如果这个数量大于等于 ，则说明存在满足条件的子字符串。此时需要判断字符串从右端点 向左移动多少个位置，可以使得子字符串仍然满足条件。具体来说，右端点一共可以有 种选择方式。我们将这些数量累加到答案中。然后将指针 移动到下一个 的位置，继续枚举下一个 的值，直到 超过字符串长度为止。
时间复杂度 ，空间复杂度 ，其中 是字符串的长度。
class Solution:
def numberOfSubstrings(self, s: str) -> int:
n = len(s)
nxt = [n] * (n + 1)
for i in range(n - 1, -1, -1):
nxt[i] = nxt[i + 1]
if s[i] == "0":
nxt[i] = i
ans = 0
for i in range(n):
cnt0 = int(s[i] == "0")
j = i
while j < n and cnt0 * cnt0 <= n:
cnt1 = (nxt[j + 1] - i) - cnt0
if cnt1 >= cnt0 * cnt0:
ans += min(nxt[j + 1] - j, cnt1 - cnt0 * cnt0 + 1)
j = nxt[j + 1]
cnt0 += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for familiarity with the sliding window technique.
- question_mark
Expect the candidate to handle edge cases like all zeros or all ones efficiently.
- question_mark
The ability to explain time and space complexity in the context of the sliding window pattern is crucial.
常见陷阱
外企场景- error
Not updating the running count of ones and zeros correctly within the window.
- error
Over-complicating the approach, leading to a higher time complexity than necessary.
- error
Failing to account for all valid substrings when determining the count.
进阶变体
外企场景- arrow_right_alt
Count substrings with dominant ones in a binary string with additional constraints, such as specific length or pattern restrictions.
- arrow_right_alt
Use a more optimized version of the sliding window algorithm to reduce space complexity.
- arrow_right_alt
Expand the problem to consider substrings with dominant ones in non-binary strings, applying a similar sliding window approach.