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 <= 10^5
  • s 只包含 '0' 和 '1'
  • 0 <= numOps <= n

解题思路

这是一个典型的二分查找答案的问题。我们需要找到能够达到的最小连续相同字符长度。

解题思路：

  1. 二分查找框架：答案范围在 [1, n] 之间，我们二分查找能够达到的最小长度。

  2. 检查函数的核心逻辑：对于给定的长度 mid，我们需要验证是否能用不超过 numOps 次操作达到目标。

  3. 分组策略：将连续相同字符分组，每组最多包含 mid 个字符。如果某组超过 mid 个字符，我们需要在适当位置翻转字符来打断连续性。

  4. 操作策略：

    • 对于长度超过 mid 的连续段，我们将其分成若干个长度为 mid 的块
    • 在每个块的末尾翻转字符，这样可以最有效地打断连续性
    • 对于最后一个不完整的块，如果长度 ≥ mid，也需要一次翻转

  5. 特殊情况处理：

    • 当目标长度为 1 时，我们需要创建交替模式（如 “0101” 或 “1010”）
    • 计算两种模式所需的最小操作次数

时间复杂度：O(n log n)，其中二分查找 O(log n)，每次检查 O(n)。

空间复杂度：O(1)，只使用常数额外空间。

代码实现

class Solution {
public:
    int minLength(string s, int numOps) {
        int n = s.length();
        
        auto canAchieve = [&](int maxLen) -> bool {
            if (maxLen == 1) {
                // 特殊情况：目标长度为1，需要交替模式
                int ops1 = 0, ops2 = 0;
                for (int i = 0; i < n; i++) {
                    if (s[i] != '0' + (i % 2)) ops1++;
                    if (s[i] != '1' - (i % 2)) ops2++;
                }
                return min(ops1, ops2) <= numOps;
            }
            
            int ops = 0;
            int i = 0;
            
            while (i < n) {
                int j = i;
                // 找到连续相同字符的结束位置
                while (j < n && s[j] == s[i]) {
                    j++;
                }
                
                int len = j - i;
                if (len > maxLen) {
                    // 需要打断这个连续段
                    ops += len / (maxLen + 1);
                }
                
                i = j;
            }
            
            return ops <= numOps;
        };
        
        int left = 1, right = n;
        int result = n;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canAchieve(mid)) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
};

class Solution:
    def minLength(self, s: str, numOps: int) -> int:
        n = len(s)
        
        def canAchieve(maxLen):
            if maxLen == 1:
                # 特殊情况：目标长度为1，需要交替模式
                ops1 = sum(1 for i in range(n) if s[i] != str(i % 2))
                ops2 = sum(1 for i in range(n) if s[i] != str(1 - i % 2))
                return min(ops1, ops2) <= numOps
            
            ops = 0
            i = 0
            
            while i < n:
                j = i
                # 找到连续相同字符的结束位置
                while j < n and s[j] == s[i]:
                    j += 1
                
                length = j - i
                if length > maxLen:
                    # 需要打断这个连续段
                    ops += length // (maxLen + 1)
                
                i = j
            
            return ops <= numOps
        
        left, right = 1, n
        result = n
        
        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;
        
        bool CanAchieve(int maxLen) {
            if (maxLen == 1) {
                // 特殊情况：目标长度为1，需要交替模式
                int ops1 = 0, ops2 = 0;
                for (int i = 0; i < n; i++) {
                    if (s[i] != (char)('0' + i % 2)) ops1++;
                    if (s[i] != (char)('1' - i % 2)) ops2++;
                }
                return Math.Min(ops1, ops2) <= numOps;
            }
            
            int ops = 0;
            int i = 0;
            
            while (i < n) {
                int j = i;
                // 找到连续相同字符的结束位置
                while (j < n && s[j] == s[i]) {
                    j++;
                }
                
                int length = j - i;
                if (length > maxLen) {
                    // 需要打断这个连续段
                    ops += length / (maxLen + 1);
                }
                
                i = j;
            }
            
            return ops <= numOps;
        }
        
        int left = 1, right = n;
        int result = n;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (CanAchieve(mid)) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
}

var minLength = function(s, numOps) {
    const n = s.length;
    
    function canAchieve(maxLen) {
        let minOps = Infinity;
        
        // Try both patterns: starting with '0' and starting with '1'
        for (let startChar of ['0', '1']) {
            let ops = 0;
            let i = 0;
            
            while (i < n) {
                // Find the start of a segment that needs to be broken
                let segmentStart = i;
                let expectedChar = startChar;
                if (maxLen > 1) {
                    // Skip to find segments longer than maxLen
                    while (i < n && s[i] === s[segmentStart] && i - segmentStart < maxLen) {
                        i++;
                    }
                    
                    if (i < n && s[i] === s[segmentStart]) {
                        // Found a segment longer than maxLen, need to break it
                        let segmentEnd = i;
                        while (segmentEnd < n && s[segmentEnd] === s[segmentStart]) {
                            segmentEnd++;
                        }
                        
                        // Calculate minimum operations to break this segment
                        let segmentLen = segmentEnd - segmentStart;
                        ops += Math.floor(segmentLen / (maxLen + 1));
                        i = segmentEnd;
                    }
                } else {
                    // maxLen = 1, use alternating pattern
                    let targetChar = (i % 2 === 0) ? startChar : (startChar === '0' ? '1' : '0');
                    if (s[i] !== targetChar) {
                        ops++;
                    }
                    i++;
                }
            }
            
            minOps = Math.min(minOps, ops);
        }
        
        return minOps <= numOps;
    }
    
    let left = 1, right = n;
    let result = n;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (canAchieve(mid)) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度数值
时间复杂度O(n log n)
空间复杂度O(1)