最长有效括号匹配子串的变种——允许一次失配的最长有效括号子串 题目描述： 给定一个只包含 '(' 和 ')' 的字符串 s，找出最长的有效括号子串的长度，但允许最多一次"失配"。所谓失配，指的是可以将一个括号从 '(' 改为 ')' 或者从 ')' 改为 '('，使得整个子串变成有效的括号串。 解题过程： 问题分析： 标准的最长有效括号子串问题要求完全匹配 本题允许修改一个字符，这增加了问题的灵活性 我们需要找到最长的子串，在最多修改一个字符的情况下能变成有效括号串 关键观察： 有效括号串的平衡条件：从左到右扫描时，左括号数始终 ≥ 右括号数，且最终左右括号数相等 允许一次失配意味着：我们可以容忍一次"不平衡"的情况 动态规划定义： 定义 dp[ i][ 0 ]：以 i 结尾的子串，在没有任何修改情况下的平衡度（左括号比右括号多的数量） 定义 dp[ i][ 1 ]：以 i 结尾的子串，在使用了一次修改权后的平衡度 状态转移方程： 基本情况：dp[ 0][ 0 ] = 0 或 1（取决于第一个字符） 对于每个位置 i： 如果 s[ i ] == '('： dp[ i][ 0] = dp[ i-1][ 0 ] + 1 // 没有使用修改权，遇到左括号 dp[ i][ 1] = max(dp[ i-1][ 1] + 1, dp[ i-1][ 0 ] - 1) // 使用修改权的情况：要么之前已用过修改权，要么现在使用（将'('改为')'） 如果 s[ i ] == ')'： dp[ i][ 0] = dp[ i-1][ 0 ] - 1 // 没有使用修改权，遇到右括号 dp[ i][ 1] = max(dp[ i-1][ 1] - 1, dp[ i-1][ 0 ] + 1) // 使用修改权的情况：要么之前已用过修改权，要么现在使用（将')'改为'('） 有效子串的判断： 当 dp[ i][ 0 ] == 0 时，说明从某个起点到 i 的子串是有效括号串 当 dp[ i][ 1 ] == 0 时，说明从某个起点到 i 的子串在使用一次修改后是有效括号串 我们需要记录满足条件时的最大长度 具体实现步骤： 初始化 dp 数组，长度为 n 维护一个栈来记录可能的起点位置 遍历字符串，更新 dp 值 当平衡度为负时，需要重置起点 记录满足 dp[ i][ 0] == 0 或 dp[ i][ 1 ] == 0 时的最大长度 时间复杂度：O(n)，空间复杂度：O(n) 这个算法通过动态规划巧妙地处理了一次修改权的情况，既考虑了修改当前字符的情况，也考虑了之前已经使用过修改权的情况。