线性动态规划：最长有效括号匹配子串的变种——允许一次失配的最长有效括号子串

题目描述
给定一个仅由 '(' 和 ')' 组成的字符串 s，允许你最多修改一个字符（将 '(' 改为 ')' 或反之），求修改后能得到的最长有效括号子串的长度。例如：

• 输入 s = "()())"，将最后一个 ')' 改为 '(' 得到 "()()("，最长有效子串为 "()()"，长度为 4。
• 输入 s = "(()"，将第一个 '(' 改为 ')' 得到 "())"，最长有效子串为 "()"，长度为 2。

解题思路
此问题在经典“最长有效括号子串”动态规划解法基础上，增加一次失配机会。我们可以定义两个动态规划数组，分别记录未使用修改和已使用修改时的状态。

步骤 1：状态定义

设 dp0[i] 表示以 s[i] 结尾的、未使用修改的最长有效括号子串长度。
设 dp1[i] 表示以 s[i] 结尾的、已使用一次修改的最长有效括号子串长度。

初始化：dp0[0] = 0, dp1[0] = 0（单个字符无法构成有效括号对）。

步骤 2：状态转移（分情况讨论）

遍历字符串 s（索引从 1 开始），对每个字符 s[i]：

情况 1：当前字符为 ')'

1. 未使用修改（dp0[i]）：

   • 若 s[i-1] = '('，则 dp0[i] = dp0[i-2] + 2（形成 "()"）。
   • 若 s[i-1] = ')' 且 i - dp0[i-1] - 1 >= 0 且 s[i - dp0[i-1] - 1] = '('，则：
     dp0[i] = dp0[i-1] + 2 + dp0[i - dp0[i-1] - 2]（嵌套或连接有效子串）。
   • 否则 dp0[i] = 0。

2. 已使用修改（dp1[i]）：

   • 方案 A：当前字符 ')' 不改动，但之前已用过修改权：
     类似 dp0[i] 的逻辑，但用 dp1 替代部分 dp0：
     • 若 s[i-1] = '('，则 dp1[i] = dp1[i-2] + 2。
     • 若 s[i-1] = ')' 且 i - dp1[i-1] - 1 >= 0 且 s[i - dp1[i-1] - 1] = '('，则：
       dp1[i] = dp1[i-1] + 2 + dp1[i - dp1[i-1] - 2]。
     • 否则尝试方案 B。
   • 方案 B：当前字符 ')' 改为 '('（消耗修改权）：
     此时 s[i] 变为 '('，无法以 '(' 结尾形成有效子串，故 dp1[i] = 0。
   • 取两种方案的最大值。

情况 2：当前字符为 '('

1. 未使用修改（dp0[i]）：

   • 以 '(' 结尾无法形成有效子串，故 dp0[i] = 0。

2. 已使用修改（dp1[i]）：

   • 方案 A：当前字符 '(' 不改动，但之前已用过修改权：
     同 dp0[i] 逻辑，但以 '(' 结尾仍无效，故为 0。
   • 方案 B：当前字符 '(' 改为 ')'（消耗修改权）：
     此时相当于字符是 ')'，可套用 dp0[i] 中 ')' 的逻辑，但需注意之前状态应为未使用修改（因为修改用在当前）：
     • 若 s[i-1] = '('，则 dp1[i] = dp0[i-2] + 2。
     • 若 s[i-1] = ')' 且 i - dp0[i-1] - 1 >= 0 且 s[i - dp0[i-1] - 1] = '('，则：
       dp1[i] = dp0[i-1] + 2 + dp0[i - dp0[i-1] - 2]。
     • 否则 dp1[i] = 0。

步骤 3：示例推导（s = "()())"）

索引：0: '(', 1: ')', 2: '(', 3: ')', 4: ')'

• i=1：s[1]=')'，与 s[0]='(' 匹配，dp0[1]=2，dp1[1]=0（无需修改）。
• i=2：'('，dp0[2]=0，dp1[2]：改为 ')' 后与 s[1]=')' 不匹配，但 s[0]='(' 与当前（改后）匹配？需检查 i=2 改为 ')' 后：s[1]=')' 和 s[2]=')' 无法匹配，故 dp1[2]=0。
• i=3：')'，与 s[2]='(' 匹配，dp0[3]=dp0[1]+2=2+2=4（"()()"），dp1[3] 同逻辑得 4。
• i=4：')'，dp0[4]：s[3]=')'，检查 i- dp0[3]-1 = 4-4-1=-1 越界，故 dp0[4]=0。
  dp1[4]：方案 A（已用修改权）同 dp0[4] 逻辑但用 dp1 得 0；方案 B（当前改 '('）：改为 '(' 后，s[4]='(' 无效，故 0。
  但正确做法应为：i=4 改为 '(' 后，s[3]=')' 与它匹配？形成 "()"，但前面 i=2 是 '('，i=1 是 ')'，整体 "()()(" 最长有效为 "()()" 长度 4。这里需注意：修改后可能使前面一段连接成更长有效子串，因此需检查 i - dp0[i-1] - 1 的边界。

实际计算时，需同时维护 dp0 和 dp1，并在每一步取最大值：
max_len = max(max_len, dp0[i], dp1[i])。

步骤 4：算法实现要点

• 遍历时需判断下标越界，将负索引对应的 dp 值视为 0。
• 注意 dp0 和 dp1 在转移时的相互依赖关系。
• 时间复杂度 O(n)，空间复杂度 O(n)。

核心代码逻辑（伪代码）：

n = len(s)
dp0 = [0] * n
dp1 = [0] * n
ans = 0
for i in range(1, n):
    if s[i] == ')':
        # 计算 dp0[i]
        if s[i-1] == '(':
            dp0[i] = (dp0[i-2] if i>=2 else 0) + 2
        else:
            j = i - dp0[i-1] - 1
            if j >= 0 and s[j] == '(':
                dp0[i] = dp0[i-1] + 2 + (dp0[j-1] if j-1>=0 else 0)
        # 计算 dp1[i]
        # 方案A：已用过修改权
        candA = 0
        if s[i-1] == '(':
            candA = (dp1[i-2] if i>=2 else 0) + 2
        else:
            j = i - dp1[i-1] - 1
            if j >= 0 and s[j] == '(':
                candA = dp1[i-1] + 2 + (dp1[j-1] if j-1>=0 else 0)
        # 方案B：当前修改
        candB = 0
        # 当前 ')' 改为 '('，则 s[i]='('，无效，故 candB=0
        dp1[i] = max(candA, candB)
    else:  # s[i] == '('
        dp0[i] = 0
        # 计算 dp1[i]
        # 方案A：已用过修改权，且当前为 '('，无效
        candA = 0
        # 方案B：当前改为 ')'
        candB = 0
        if i-1 >= 0:
            if s[i-1] == '(':
                candB = (dp0[i-2] if i>=2 else 0) + 2
            else:
                j = i - dp0[i-1] - 1
                if j >= 0 and s[j] == '(':
                    candB = dp0[i-1] + 2 + (dp0[j-1] if j-1>=0 else 0)
        dp1[i] = max(candA, candB)
    ans = max(ans, dp0[i], dp1[i])
return ans

总结

本题通过扩展经典动态规划状态，区分是否使用修改权，从而在 O(n) 时间内求解允许一次失配的最长有效括号子串。关键点在于细致处理两种状态的转移逻辑，并注意修改操作对前后字符匹配的影响。