Easy

题目描述

给你一个由 '0' 和 '1' 组成的二进制字符串 s。

如果一个子串中所有的 '0' 都在 '1' 之前，并且 '0' 的数量等于 '1' 的数量，则认为这个子串是平衡的。注意，空子串被认为是平衡的。

返回 s 中最长平衡子串的长度。

子串是字符串中连续的字符序列。

示例 1：

输入：s = "01000111"
输出：6
解释：最长的平衡子串是 "000111"，长度为 6。

示例 2：

输入：s = "00111"
输出：4
解释：最长的平衡子串是 "0011"，长度为 4。

示例 3：

输入：s = "111"
输出：0
解释：除了空子串外，没有其他平衡子串，所以答案是 0。

约束条件：

  • 1 <= s.length <= 50
  • s[i] 为 '0' 或 '1'

提示：

  • 考虑遍历每个子数组并检查它是否平衡。
  • 在所有平衡的子数组中，答案是其中最长的一个。

解题思路

这道题要求找到最长的平衡子串，即所有 '0' 都在 '1' 之前且 '0' 和 '1' 的数量相等的子串。

方法一：暴力枚举（推荐） 由于字符串长度最大为50，我们可以枚举所有可能的子串，检查每个子串是否平衡。对于每个子串，需要满足两个条件：

  1. 所有 '0' 都在 '1' 之前
  2. '0' 和 '1' 的数量相等

时间复杂度虽然是O(n³)，但在数据规模较小的情况下完全可以接受。

方法二：优化枚举 我们可以枚举每个可能的起始位置，然后向右扩展，在扩展过程中维护 '0' 和 '1' 的计数。当遇到 '1' 后再遇到 '0' 时，当前的搜索就可以结束了，因为不满足"所有 '0' 都在 '1' 之前"的条件。

方法三：一次遍历 我们可以通过一次遍历来解决。维护当前连续的 '0' 的数量和当前连续的 '1' 的数量，当遇到完整的"0…01…1"模式时，更新答案。

代码实现

class Solution {
public:
    int findTheLongestBalancedSubstring(string s) {
        int n = s.length();
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            int zeros = 0, ones = 0;
            bool seenOne = false;
            
            for (int j = i; j < n; j++) {
                if (s[j] == '0') {
                    if (seenOne) break; // 在1后面又遇到0，不平衡
                    zeros++;
                } else {
                    seenOne = true;
                    ones++;
                }
                
                if (zeros == ones && zeros > 0) {
                    maxLen = max(maxLen, zeros + ones);
                }
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def findTheLongestBalancedSubstring(self, s: str) -> int:
        n = len(s)
        max_len = 0
        
        for i in range(n):
            zeros = 0
            ones = 0
            seen_one = False
            
            for j in range(i, n):
                if s[j] == '0':
                    if seen_one:
                        break  # 在1后面又遇到0，不平衡
                    zeros += 1
                else:
                    seen_one = True
                    ones += 1
                
                if zeros == ones and zeros > 0:
                    max_len = max(max_len, zeros + ones)
        
        return max_len

public class Solution {
    public int FindTheLongestBalancedSubstring(string s) {
        int n = s.Length;
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            int zeros = 0, ones = 0;
            bool seenOne = false;
            
            for (int j = i; j < n; j++) {
                if (s[j] == '0') {
                    if (seenOne) break; // 在1后面又遇到0，不平衡
                    zeros++;
                } else {
                    seenOne = true;
                    ones++;
                }
                
                if (zeros == ones && zeros > 0) {
                    maxLen = Math.Max(maxLen, zeros + ones);
                }
            }
        }
        
        return maxLen;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var findTheLongestBalancedSubstring = function(s) {
    let maxLen = 0;
    let zeros = 0;
    let ones = 0;
    
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '0') {
            if (ones > 0) {
                zeros = 1;
                ones = 0;
            } else {
                zeros++;
            }
        } else {
            ones++;
            maxLen = Math.max(maxLen, Math.min(zeros, ones) * 2);
        }
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)双重循环遍历所有可能的子串起始和结束位置
空间复杂度O(1)只使用常数级别的额外空间