最长连续有效括号子串的变种——允许最多k次失配的最长连续有效括号子串 题目描述 给定一个由 '(' 和 ')' 组成的字符串 s，以及一个非负整数 k。定义「有效括号子串」为满足括号匹配规则的连续子串。本问题允许在子串中最多出现 k 次失配（即括号不匹配的情况），求满足该条件的最长连续有效括号子串的长度。 例如，对于 s = "()())()"，k = 1： 无失配时，最长有效子串为 "()()"，长度为4。 允许1次失配时，可以选取子串 "()())"（最后一个 ')' 失配），其有效长度为5（扣除失配位置后实际匹配长度为4，但题目通常允许失配位置存在，计算整个子串长度）。 解题过程 步骤1：问题分析 传统最长有效括号子串问题要求完全匹配，本题允许最多 k 次失配，即子串中最多有 k 个括号无法匹配。这需要动态规划状态记录当前匹配程度和已使用失配次数。 步骤2：状态定义 定义 dp[ i][ j] 表示以 s[ i ] 结尾的子串中，已使用 j 次失配时的最大有效长度。但直接这样定义复杂度高（O(n²)）。优化方向： 使用两个状态数组：dp_ max[ i ] 表示以 i 结尾的最大长度，并用辅助数组记录失配次数。 更高效的方法：结合栈和贪心，记录当前失配次数下的最优解。 实际采用：滑动窗口 + 双栈（用于记录左括号和失配位置）。 步骤3：滑动窗口法设计 初始化左指针 left = 0，右指针 right 从0开始遍历字符串。 维护计数器 count：遇到 '(' 加1，遇到 ')' 减1。count 表示当前窗口的匹配度。 当 count < 0 时，说明有额外右括号，可能产生失配。此时若已用失配次数小于k，则消耗一次失配机会，保持窗口扩展；否则移动左指针直到 count >= 0。 同时记录最大窗口长度 max_ len。 但需处理左括号过多情况：当窗口内左括号多于右括号超过 k 时，也需调整左指针。 步骤4：具体算法步骤 初始化 left = 0, used_ mismatch = 0, max_ len = 0。 遍历 right 从0到n-1： 如果 s[ right ] == '('，直接扩展窗口。 如果 s[ right ] == ')'，则： 若当前 count >= 0，正常扩展。 若 count < 0 且 used_ mismatch < k，消耗一次失配，used_ mismatch++，保持 right 扩展。 否则，移动 left 至第一个使 count >= 0 的位置，重置 used_ mismatch。 更新 max_ len = max(max_ len, right - left + 1)。 对称处理左括号过多情况：从右向左扫描，逻辑类似。 步骤5：复杂度分析 左右各扫描一次，时间复杂度 O(n)，空间复杂度 O(1)。 示例验证 s = "()())()", k = 1： 右扫描：到 right=4 时，count=-1，消耗1次失配，得到子串 "()())" 长度5。 左扫描：无更优解。 最终结果：5。 此方法通过动态调整窗口边界和失配次数，高效求解允许失配的最长有效括号子串。