最长有效括号匹配子串的变种——允许最多k次失配的最长有效括号子串

题目描述
给定一个只包含'('和')'的字符串s和一个非负整数k，请找出最长的子串，使得这个子串在最多允许k次字符替换（将'('改为')'或将')'改为'('）的情况下，能够变成一个完全有效的括号字符串。返回这个最长子串的长度。

解题思路
这个问题是经典最长有效括号问题的扩展，增加了允许最多k次失配的灵活性。我们需要找到一种动态规划方法来跟踪匹配状态和已使用的修改次数。

关键观察

1. 有效括号序列的核心是平衡性：任意位置左括号数量≥右括号数量，最终左右括号数量相等
2. 允许k次修改意味着我们可以容忍一定的不平衡，但需要记录已使用的修改次数
3. 我们需要同时考虑从左到右和从右到左两个方向的扫描，因为括号匹配具有方向性

动态规划解法

步骤1：定义状态
定义dp[i][j]表示以位置i结尾的子串，在使用了j次修改的情况下，能够形成的最大有效括号长度。

但是这种定义在实现时比较复杂，我们可以采用更实用的方法：

步骤2：从左到右扫描
我们维护两个变量：

• left：左括号数量（包括被修改为左括号的）
• right：右括号数量（包括被修改为右括号的）
• used：已使用的修改次数

从左到右遍历字符串，对于每个字符：

• 如果是'('，left++
• 如果是')'，right++

如果right > left + (k - used)，说明当前不平衡且无法通过剩余修改次数弥补，需要调整窗口。

步骤3：滑动窗口实现
使用双指针left_ptr和right_ptr表示当前窗口：

1. 初始化left_ptr = 0, right_ptr = 0
2. 当right_ptr < n时：
   • 根据当前字符更新left或right计数
   • 如果right > left + (k - used)，需要收缩左边界
   • 否则，更新最大长度

步骤4：从右到左扫描
由于括号匹配的对称性，我们还需要从右到左扫描一次：

• 这次扫描中，我们关注右括号数量不能超过左括号数量过多

具体算法实现

def longestValidParenthesesWithKMismatches(s, k):
    n = len(s)
    max_len = 0
    
    # 从左到右扫描
    left = right = used = 0
    left_ptr = 0
    
    for right_ptr in range(n):
        if s[right_ptr] == '(':
            left += 1
        else:
            right += 1
        
        # 如果右括号过多，考虑使用修改次数
        while right > left + (k - used) and left_ptr <= right_ptr:
            if s[left_ptr] == '(':
                left -= 1
            else:
                right -= 1
            left_ptr += 1
        
        # 如果当前窗口可以形成有效括号
        if left + right - used <= k or abs(left - right) <= (k - used):
            max_len = max(max_len, right_ptr - left_ptr + 1)
    
    # 从右到左扫描（处理左括号过多的情况）
    left = right = used = 0
    right_ptr = n - 1
    
    for left_ptr in range(n - 1, -1, -1):
        if s[left_ptr] == '(':
            left += 1
        else:
            right += 1
        
        # 如果左括号过多，考虑使用修改次数
        while left > right + (k - used) and left_ptr <= right_ptr:
            if s[right_ptr] == '(':
                left -= 1
            else:
                right -= 1
            right_ptr -= 1
        
        # 如果当前窗口可以形成有效括号
        if left + right - used <= k or abs(left - right) <= (k - used):
            max_len = max(max_len, right_ptr - left_ptr + 1)
    
    return max_len

步骤5：复杂度分析

• 时间复杂度：O(n)，我们进行了两次线性扫描
• 空间复杂度：O(1)，只使用了常数级别的额外空间

示例验证
例1：s = "()())", k = 1

• 从左到右扫描：找到"()()"，长度4
• 从右到左扫描：结果相同
• 输出：4

例2：s = ")(())))", k = 2

• 可以修改前两个字符形成"((()))"，长度6
• 输出：6

这个算法通过双向扫描和滑动窗口技术，高效地解决了允许k次失配的最长有效括号子串问题。