LeetCode 3713题解析：暴力枚举法求最长平衡子串-尧图网络科技

1. 题目解析与暴力枚举思路

今天我们来拆解LeetCode第3713题"最长的平衡子串 I"。这是一道典型的字符串处理题目，要求我们找到一个二进制字符串中最长的平衡子串。所谓平衡子串，指的是子串中0和1的数量相等。

先看题目给出的示例：输入："11010111" 输出：4 解释：最长平衡子串是"1010"，长度为4

1.1 暴力枚举的核心思想

暴力枚举（Brute Force）是最直观的解题方法，它的核心思路是：

枚举所有可能的子串
检查每个子串是否满足平衡条件
记录满足条件的最长子串长度

这种方法的优势在于思路简单直接，不需要复杂的数学推导，特别适合作为解题的第一思路。虽然时间复杂度较高（O(n²)），但对于长度不大的字符串（比如n≤1000）完全可行。

注意：在面试或竞赛中，先给出暴力解法再优化是常见的解题策略，这展示了你的思考过程。

2. 暴力枚举的代码实现

2.1 Python实现详解

让我们用Python来实现这个暴力解法：

def findTheLongestBalancedSubstring(s: str) -> int: max_len = 0 n = len(s) for i in range(n): count0 = 0 count1 = 0 for j in range(i, n): if s[j] == '0': count0 += 1 else: count1 += 1 if count0 == count1: max_len = max(max_len, j - i + 1) return max_len

代码解析：

外层循环变量i表示子串的起始位置
内层循环变量j表示子串的结束位置
count0和count1分别统计子串中0和1的数量
当count0 == count1时，更新最大长度

2.2 时间复杂度分析

这个解法的时间复杂度是O(n²)，因为有两层嵌套循环：

外层循环执行n次
内层循环平均执行n/2次
总时间复杂度为O(n²)

空间复杂度是O(1)，只使用了常数个额外变量。

3. 暴力解法的优化空间

虽然暴力解法能解决问题，但我们还是可以做一些小优化：

3.1 提前终止内层循环

当剩余字符串长度小于当前max_len时，可以直接终止内层循环：

for i in range(n): if n - i <= max_len: break # 其余代码不变

这个优化可以避免一些不必要的计算。

3.2 从最长子串开始检查

我们可以从最长的可能子串开始检查，一旦找到平衡子串就可以立即返回：

def findTheLongestBalancedSubstring(s: str) -> int: n = len(s) for l in range(n, 0, -1): # 从最长开始 for i in range(n - l + 1): j = i + l - 1 # 检查s[i..j]是否平衡 if s[i:j+1].count('0') == s[i:j+1].count('1'): return l return 0

这种方法在最坏情况下仍然是O(n²)，但在实际应用中可能更快找到解。