LeetCode 题解工作台
最长平衡子字符串
给你一个仅由 0 和 1 组成的二进制字符串 s 。 如果子字符串中 所有的 0 都在 1 之前 且其中 0 的数量等于 1 的数量，则认为 s 的这个子字符串是平衡子字符串。请注意，空子字符串也视作平衡子字符串。 返回 s 中最长的平衡子字符串长度。 子字符串是字符串中的一个连续字符序列。 示例 …
1
题型
6
代码语言
3
相关题
当前训练重点
简单 · String-driven solution strategy
答案摘要
注意到数据范围很小，因此，我们可以枚举所有的子串 ，检查其是否为平衡子串，如果是，则更新答案。 时间复杂度 ，空间复杂度 。其中 为字符串 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 String-driven solution strategy 题型思路
题目描述
给你一个仅由 0 和 1 组成的二进制字符串 s 。
如果子字符串中 所有的 0 都在 1 之前 且其中 0 的数量等于 1 的数量，则认为 s 的这个子字符串是平衡子字符串。请注意，空子字符串也视作平衡子字符串。
返回 s 中最长的平衡子字符串长度。
子字符串是字符串中的一个连续字符序列。
示例 1：
输入：s = "01000111" 输出：6 解释：最长的平衡子字符串是 "000111" ，长度为 6 。
示例 2：
输入：s = "00111"
输出：4
解释：最长的平衡子字符串是 "0011" ，长度为 4 。
示例 3：
输入：s = "111" 输出：0 解释：除了空子字符串之外不存在其他平衡子字符串，所以答案为 0 。
提示：
1 <= s.length <= 50'0' <= s[i] <= '1'
解题思路
方法一：暴力枚举
注意到数据范围很小，因此，我们可以枚举所有的子串 ，检查其是否为平衡子串，如果是，则更新答案。
时间复杂度 ，空间复杂度 。其中 为字符串 的长度。
class Solution:
def findTheLongestBalancedSubstring(self, s: str) -> int:
def check(i, j):
cnt = 0
for k in range(i, j + 1):
if s[k] == '1':
cnt += 1
elif cnt:
return False
return cnt * 2 == (j - i + 1)
n = len(s)
ans = 0
for i in range(n):
for j in range(i + 1, n):
if check(i, j):
ans = max(ans, j - i + 1)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate is familiar with string manipulation and optimization strategies.
- question_mark
The candidate can implement efficient substring checks with prefix sum or sliding window.
- question_mark
The candidate can distinguish between brute force and optimized approaches.
常见陷阱
外企场景- error
Incorrectly counting zeroes and ones in a substring.
- error
Overlooking cases where no balanced substring exists.
- error
Not considering the empty substring as balanced in the edge cases.
进阶变体
外企场景- arrow_right_alt
Handling edge cases with no balanced substrings.
- arrow_right_alt
Optimizing with different window sizes.
- arrow_right_alt
Applying different balancing rules such as alternating zeroes and ones.