Medium

题目描述

给定一个只包含字符 ‘0’ 和 ‘1’ 的二进制字符串 s。

如果一个字符串包含相等数量的 ‘0’ 和 ‘1’，则称该字符串是平衡的。

你最多可以在 s 中任意两个字符之间执行一次交换。然后，从 s 中选择一个平衡子串。

返回一个整数，表示你可以选择的平衡子串的最大长度。

示例 1：

输入：s = "100001"
输出：4
解释：
交换 "100001"。字符串变成 "101000"。
选择子串 "1010"，它是平衡的，因为它有两个 '0' 和两个 '1'。

示例 2：

输入：s = "111"
输出：0
解释：
选择不执行任何交换。
选择空子串，它是平衡的，因为它有零个 '0' 和零个 '1'。

约束条件：

  • 1 <= s.length <= 10^5
  • s 只包含字符 ‘0’ 和 ‘1’

提示：

  • 平衡子串具有相同数量的 0 和 1
  • 即使经过一次交换，答案也不能超过 2 * min(cnt0, cnt1)
  • 只有当交换能够改善所选窗口时，交换才有用
  • 寻找一个子串，其平衡性可以通过移入或移出一个不匹配字符来修复
  • 跟踪前缀平衡并检查在一次交换后有效段可以扩展多远

解题思路

这道题需要在最多一次字符交换后，找到最长的平衡子串。我们可以从两个角度来思考：

  1. 不交换的情况：直接遍历所有可能的子串，找到最长的平衡子串。

  2. 交换一次的情况：关键洞察是，如果我们要通过交换来改善某个子串的平衡性，那么这个子串在交换前应该恰好"差一个字符"就能平衡。

具体思路是使用前缀平衡来优化。定义 balance[i] 为前 i 个字符中 ‘1’ 的数量减去 ‘0’ 的数量。对于区间 [i,j]，如果 balance[j] - balance[i-1] = 0，则该区间是平衡的。

对于交换的情况，我们枚举每个可能的交换操作（即交换位置 i 和 j 的字符），然后检查交换后能得到的最长平衡子串。为了优化，我们可以观察到：

  • 如果交换 ‘0’ 和 ‘1’，会影响它们之间所有位置的前缀平衡值
  • 我们需要找到交换后能形成 balance[r] - balance[l-1] = 0 的最长区间

算法步骤：

  1. 计算原始字符串的前缀平衡数组
  2. 不交换情况下找最长平衡子串
  3. 枚举所有可能的交换位置，计算交换后的最长平衡子串
  4. 返回所有情况中的最大值

代码实现

class Solution {
public:
    int longestBalanced(string s) {
        int n = s.length();
        vector<int> balance(n + 1, 0);
        
        // 计算前缀平衡
        for (int i = 0; i < n; i++) {
            balance[i + 1] = balance[i] + (s[i] == '1' ? 1 : -1);
        }
        
        int maxLen = 0;
        
        // 不交换的情况
        unordered_map<int, int> firstOccur;
        firstOccur[0] = 0;
        for (int i = 1; i <= n; i++) {
            if (firstOccur.count(balance[i])) {
                maxLen = max(maxLen, i - firstOccur[balance[i]]);
            } else {
                firstOccur[balance[i]] = i;
            }
        }
        
        // 交换的情况
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (s[i] != s[j]) { // 只有不同字符的交换才有意义
                    // 交换后重新计算这段区间的影响
                    int diff = (s[i] == '0') ? 2 : -2;
                    
                    unordered_map<int, int> newFirstOccur;
                    newFirstOccur[0] = 0;
                    int currentMax = maxLen;
                    
                    for (int k = 1; k <= n; k++) {
                        int newBalance = balance[k];
                        if (k > i && k <= j) {
                            newBalance += diff;
                        }
                        
                        if (newFirstOccur.count(newBalance)) {
                            currentMax = max(currentMax, k - newFirstOccur[newBalance]);
                        } else {
                            newFirstOccur[newBalance] = k;
                        }
                    }
                    
                    maxLen = max(maxLen, currentMax);
                }
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def longestBalanced(self, s: str) -> int:
        n = len(s)
        balance = [0] * (n + 1)
        
        # 计算前缀平衡
        for i in range(n):
            balance[i + 1] = balance[i] + (1 if s[i] == '1' else -1)
        
        max_len = 0
        
        # 不交换的情况
        first_occur = {0: 0}
        for i in range(1, n + 1):
            if balance[i] in first_occur:
                max_len = max(max_len, i - first_occur[balance[i]])
            else:
                first_occur[balance[i]] = i
        
        # 交换的情况
        for i in range(n):
            for j in range(i + 1, n):
                if s[i] != s[j]:  # 只有不同字符的交换才有意义
                    # 交换后重新计算这段区间的影响
                    diff = 2 if s[i] == '0' else -2
                    
                    new_first_occur = {0: 0}
                    current_max = max_len
                    
                    for k in range(1, n + 1):
                        new_balance = balance[k]
                        if i < k <= j:
                            new_balance += diff
                        
                        if new_balance in new_first_occur:
                            current_max = max(current_max, k - new_first_occur[new_balance])
                        else:
                            new_first_occur[new_balance] = k
                    
                    max_len = max(max_len, current_max)
        
        return max_len

public class Solution {
    public int LongestBalanced(string s) {
        int n = s.Length;
        int[] balance = new int[n + 1];
        
        // 计算前缀平衡
        for (int i = 0; i < n; i++) {
            balance[i + 1] = balance[i] + (s[i] == '1' ? 1 : -1);
        }
        
        int maxLen = 0;
        
        // 不交换的情况
        Dictionary<int, int> firstOccur = new Dictionary<int, int>();
        firstOccur[0] = 0;
        for (int i = 1; i <= n; i++) {
            if (firstOccur.ContainsKey(balance[i])) {
                maxLen = Math.Max(maxLen, i - firstOccur[balance[i]]);
            } else {
                firstOccur[balance[i]] = i;
            }
        }
        
        // 交换的情况
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (s[i] != s[j]) { // 只有不同字符的交换才有意义
                    // 交换后重新计算这段区间的影响
                    int diff = (s[i] == '0') ? 2 : -2;
                    
                    Dictionary<int, int> newFirstOccur = new Dictionary<int, int>();
                    newFirstOccur[0] = 0;
                    int currentMax = maxLen;
                    
                    for (int k = 1; k <= n; k++) {
                        int newBalance = balance[k];
                        if (k > i && k <= j) {
                            newBalance += diff;
                        }
                        
                        if (newFirstOccur.ContainsKey(newBalance)) {
                            currentMax = Math.Max(currentMax, k - newFirstOccur[newBalance]);
                        } else {
                            newFirstOccur[newBalance] = k;
                        }
                    }
                    
                    maxLen = Math.Max(maxLen, currentMax);
                }
            }
        }
        
        return maxLen;
    }
}

var longestBalanced = function(s) {
    const n = s.length;
    const balance = new Array(n + 1).fill(0);
    
    // 计算前缀平衡
    for (let i = 0; i < n; i++) {
        balance[i + 1] = balance[i] + (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n³)
空间复杂度O(n)

注：其中 n 是字符串长度。时间复杂度主要来自于枚举所有可能的交换位置对 O(n²)，以及对每种交换重新计算最长平衡子串 O(n)。空间复杂度主要用于存储前缀平衡数组和哈希表。