Hard

题目描述

给你一个长度为 n 的二进制字符串 s 和一个整数 numOps。

你可以对 s 执行以下操作最多 numOps 次：

  • 选择任意索引 i（其中 0 <= i < n）并翻转 s[i]。如果 s[i] == ‘1’，则将 s[i] 改为 ‘0’，反之亦然。

你需要最小化 s 的最长子串的长度，使得该子串中的所有字符都相同。

返回操作后的最小长度。

示例 1：

输入：s = "000001", numOps = 1
输出：2
解释：通过将 s[2] 改为 '1'，s 变成 "001001"。具有相同字符的最长子串是 s[0..1] 和 s[3..4]。

示例 2：

输入：s = "0000", numOps = 2
输出：1
解释：通过将 s[0] 和 s[2] 改为 '1'，s 变成 "1010"。

示例 3：

输入：s = "0101", numOps = 0
输出：1

约束条件：

  • 1 <= n == s.length <= 1000
  • s 只包含 ‘0’ 和 ‘1’
  • 0 <= numOps <= n

提示：

  • 可以在这里使用二分查找吗？
  • 对预测函数使用动态规划

解题思路

这道题需要找到操作后最长相同字符子串的最小值。我们可以使用二分查找加动态规划的方法来解决。

核心思路：

  1. 使用二分查找答案：对最长相同字符子串的长度进行二分搜索，范围是 [1, n]
  2. 对于每个候选长度 k，检查是否可能在 numOps 次操作内使所有相同字符子串长度都不超过 k
  3. 检查函数使用动态规划：考虑将字符串分割成长度不超过 k 的段，每段内字符相同

动态规划状态设计：

  • dp[i][c] 表示处理到位置 i，且第 i 位字符为 c（0或1）时的最小操作次数
  • 对于每个位置，我们可以选择保持原字符或翻转字符
  • 同时要保证当前段的长度不超过 k

优化策略：

  • 当检查长度 k 时，我们需要确保没有连续超过 k 个相同字符
  • 可以贪心地在每个长度为 k 的窗口中选择操作次数最少的方案
  • 对于每个窗口，计算变成全0或全1所需的操作次数，取较小值

时间复杂度通过二分查找优化到 O(n log n)，每次检查需要 O(n) 时间。

代码实现

class Solution {
public:
    int minLength(string s, int numOps) {
        int n = s.length();
        int left = 1, right = n;
        int result = n;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canAchieve(s, numOps, mid)) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
    
private:
    bool canAchieve(const string& s, int numOps, int maxLen) {
        int n = s.length();
        vector<vector<int>> dp(n + 1, vector<int>(2, INT_MAX));
        dp[0][0] = dp[0][1] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int c = 0; c <= 1; c++) {
                for (int len = 1; len <= min(i, maxLen); len++) {
                    if (dp[i - len][1 - c] == INT_MAX) continue;
                    
                    int cost = 0;
                    for (int j = i - len; j < i; j++) {
                        if ((s[j] - '0') != c) cost++;
                    }
                    
                    dp[i][c] = min(dp[i][c], dp[i - len][1 - c] + cost);
                }
            }
        }
        
        return min(dp[n][0], dp[n][1]) <= numOps;
    }
};

class Solution:
    def minLength(self, s: str, numOps: int) -> int:
        n = len(s)
        left, right = 1, n
        result = n
        
        def canAchieve(maxLen):
            dp = [[float('inf')] * 2 for _ in range(n + 1)]
            dp[0][0] = dp[0][1] = 0
            
            for i in range(1, n + 1):
                for c in range(2):
                    for length in range(1, min(i, maxLen) + 1):
                        if dp[i - length][1 - c] == float('inf'):
                            continue
                        
                        cost = sum(1 for j in range(i - length, i) if int(s[j]) != c)
                        dp[i][c] = min(dp[i][c], dp[i - length][1 - c] + cost)
            
            return min(dp[n][0], dp[n][1]) <= numOps
        
        while left <= right:
            mid = (left + right) // 2
            if canAchieve(mid):
                result = mid
                right = mid - 1
            else:
                left = mid + 1
        
        return result

public class Solution {
    public int MinLength(string s, int numOps) {
        int n = s.Length;
        int left = 1, right = n;
        int result = n;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (CanAchieve(s, numOps, mid)) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
    
    private bool CanAchieve(string s, int numOps, int maxLen) {
        int n = s.Length;
        int[,] dp = new int[n + 1, 2];
        
        for (int i = 0; i <= n; i++) {
            dp[i, 0] = dp[i, 1] = int.MaxValue;
        }
        dp[0, 0] = dp[0, 1] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int c = 0; c <= 1; c++) {
                for (int len = 1; len <= Math.Min(i, maxLen); len++) {
                    if (dp[i - len, 1 - c] == int.MaxValue) continue;
                    
                    int cost = 0;
                    for (int j = i - len; j < i; j++) {
                        if ((s[j] - '0') != c) cost++;
                    }
                    
                    dp[i, c] = Math.Min(dp[i, c], dp[i - len, 1 - c] + cost);
                }
            }
        }
        
        return Math.Min(dp[n, 0], dp[n, 1]) <= numOps;
    }
}

var minLength = function(s, numOps) {
    const n = s.length;
    
    function canAchieve(maxLen) {
        let minOps = Infinity;
        
        // Try pattern starting with '0'
        let ops0 = 0;
        for (let i = 0; i < n; i++) {
            let expected = Math.floor(i / maxLen) % 2 === 0 ? '0' : '1';
            if (s[i] !== expected) ops0++;
        }
        minOps = Math.min(minOps, ops0);
        
        // Try pattern starting with '1'
        let ops1 = 0;
        for (let i = 0; i < n; i++) {
            let expected = Math.floor(i / maxLen) % 2 === 0 ? '1' : '0';
            if (s[i] !== expected) ops1++;
        }
        minOps = Math.min(minOps, ops1);
        
        return minOps <= numOps;
    }
    
    let left = 1, right = n;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (canAchieve(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n² log n)，二分查找O(log n)次，每次DP检查O(n²)
空间复杂度O(n)，DP数组空间