最长有效括号匹配子串的变种——允许一次失配的最长有效括号子串
字数 5403 2025-12-23 11:55:13

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

题目描述

给定一个只包含 '(' 和 ')' 的字符串 s，找出其中最长的有效括号子串的长度，但允许最多一次“失配”（即允许有一个位置的括号不匹配，但整个子串在允许一次失配的前提下，其余括号必须能完全匹配）。
有效括号匹配的定义是：每个 '(' 都有一个对应的 ')' 与之正确配对，并且括号顺序正确。

示例
输入：s = "(()"
输出：2
解释："()" 是有效子串，但允许一次失配时，整个字符串 "(()" 如果允许第一个 '(' 失配（即不参与匹配），则 "()" 是有效的，长度为 2。

输入：s = "())"
输出：3
解释：整个字符串 "())" 允许最后一个 ')' 失配，前两个字符 "()" 有效，整体视为允许一次失配的有效子串，长度为 3。

输入：s = ")(()"
输出：2
解释：子串 "()" 是有效的，且没有失配，长度为 2。

解题过程循序渐进讲解

步骤 1：回顾经典问题（最长有效括号子串，无失配）

经典的动态规划解法定义：
dp[i] 表示以 s[i] 结尾的最长有效括号子串长度。
转移方程：

  • 如果 s[i] = ')'：
    1. 如果 s[i-1] = '('，则 dp[i] = dp[i-2] + 2（匹配一对括号，加上前面的有效长度）。
    2. 如果 s[i-1] = ')' 且 s[i - dp[i-1] - 1] = '('，则 dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]（跨越中间已匹配的部分，匹配更前面的一对括号）。
      最终答案是 max(dp[i])。

步骤 2：扩展思路，允许一次失配

我们可以在经典动态规划的基础上增加一个维度，表示“已使用的失配次数”。
定义状态：
dp[i][k] 表示以 s[i] 结尾、且使用了 k 次失配（k = 0 或 1）的最长有效括号子串长度。
注意：这里的“有效”是在允许 k 次失配的前提下，其余括号完全匹配。

关键：如何定义“失配”？
在括号匹配中，失配可以出现在两个位置：

  1. 当前位置的字符“应该匹配”但故意让它不匹配（即不参与任何配对）。
  2. 在匹配过程中，允许一个多余的左括号或右括号不参与匹配，但整个序列仍能在允许一次失配的条件下视为“有效”。

更精确地说：我们允许在整个子串中，最多有一个括号是“多余的”或“缺失的”（即无法找到匹配的对应括号），但其他括号必须完全匹配。

步骤 3：转移方程推导

我们分情况考虑 s[i] 的取值和已用失配次数 k。

情况 1：s[i] = '('

  • 如果 k = 0（尚未使用失配）：以 '(' 结尾，且前面没有失配，这个 '(' 是新的左括号，暂时没有右括号匹配它。但我们可以允许它成为一次失配吗？
    如果允许它成为失配，则状态转移到 dp[i][1]。但注意：如果我们让它失配，那么它就不参与匹配，子串长度只能从 dp[i-1][0] 继承，然后加 1（当前字符）。
    所以：
    dp[i][1] = max(dp[i][1], dp[i-1][0] + 1)（将当前 '(' 视为失配字符）。
    同时，dp[i][0] 无法更新，因为 '(' 结尾且无失配时，它没有右括号匹配，所以 dp[i][0] = 0（除非前面有某种方式让它匹配，但不可能，因为 '(' 必须在后面有 ')' 匹配，这里只考虑以 i 结尾的子串）。

  • 如果 k = 1（已用过一次失配）：当前 '(' 不能作为失配字符（因为已用过一次失配），且它没有匹配的右括号，所以 dp[i][1] = 0（以 '(' 结尾且已用过失配，无法形成有效子串）。
    但注意：有一种特殊情况，即前面的子串允许一次失配，当前 '(' 是正常的左括号，它可能需要等待后面的 ')' 来匹配，但这是以 i 结尾的子串，所以如果当前字符是 '('，它无法完成匹配，所以 dp 为 0，除非我们考虑更复杂的“等待匹配”状态，但这会使问题复杂化。
    为了简化，我们可以只考虑有效子串必须是以合法匹配结束，即最后一个字符必须是匹配成功的右括号（除了允许的一次失配可以在任意位置）。

    这样会导致：如果当前字符是 '('，那么以它结尾的子串不可能是“完全匹配（允许一次失配）”的，除非这个 '(' 本身就是那个失配字符。
    所以我们只允许在 k=0 时，将 '(' 视为失配字符，从而得到长度。

情况 2：s[i] = ')'
这是可以完成匹配的字符，分两种子情况：

子情况 2.1：s[i-1] = '('（即形如 "()"）

  • 如果 k=0：那么这对括号匹配，长度是 2，再加上前面以 i-2 结尾的最长有效子串长度（无失配）：
    dp[i][0] = dp[i-2][0] + 2。
  • 如果 k=1：
    此时已用过一次失配，这对括号可以匹配，但失配可能出现在前面某个位置。
    所以：dp[i][1] = dp[i-2][1] + 2（失配已用在前面的某处）。
    另外，还有一种可能：失配用在这个 '(' 上，即这个 '(' 是失配字符，那么当前 ')' 无法匹配，这种情况实际上不可能形成以 i 结尾的有效子串（因为右括号无匹配）。
    所以不考虑。

子情况 2.2：s[i-1] = ')'（即形如 "...))"）
设 j = i - dp[i-1][k'] - 1，其中 k' 是前面用过的失配次数。我们需要考虑前面已匹配的一段，再往前看一个字符是否能与当前 ')' 匹配。
经典无失配的公式是：如果 s[j] = '('，则 dp[i] = dp[i-1] + 2 + dp[j-1]。

现在带失配，我们分几种小情况：

(a) 不失配，正常匹配
即 s[j] = '('，且 k = k'（即失配次数不变），则：
dp[i][k] = max(dp[i][k], dp[i-1][k] + 2 + dp[j-1][k])。

(b) 将 s[j] 视为失配字符
前提是 k' = 0，且我们让 s[j] 失配，则 k 变成 1。
这样 s[j] 是 '(' 但它不参与匹配，那么当前 ')' 必须与更前面的 '(' 匹配，这需要 j 前面的有效子串，并且 s[j-1] 必须是与当前 ')' 匹配的左括号，但这样会复杂化。

实际上更简单的方法是：将失配字符的“角色”放在当前子串的任意一个位置，而不一定是 s[j]。

步骤 4：简化状态定义

为了避免复杂讨论，我们可以这样设计状态：

dp[i][k] 表示以 s[i] 结尾、且允许 k 次失配（k=0 或 1）的最长有效括号子串长度。
这里的“有效”是指：除去最多 k 个失配字符，剩下的括号序列完全匹配。

这样，我们可以用类似经典 DP 的思路，但允许在匹配过程中“跳过”一个字符（即视它为失配）。

转移方程（更系统化）：

  1. 如果 s[i] = '('：
    • 不使用失配：dp[i][0] = 0（因为 '(' 无法作为结尾完成匹配）。
    • 使用一次失配：dp[i][1] = max(dp[i][1], dp[i-1][0] + 1)（将当前 '(' 当作失配字符，所以长度+1，失配次数从0变1）。
  2. 如果 s[i] = ')'：
    • 先尝试正常匹配（不失配）：
      • 如果 s[i-1] = '('：dp[i][k] = dp[i-2][k] + 2（k=0 或 1）。
      • 否则（s[i-1] = ')'）：令 j = i - dp[i-1][k] - 1，如果 j >= 0 且 s[j] = '('，则 dp[i][k] = max(dp[i][k], dp[i-1][k] + 2 + (j-1 >= 0 ? dp[j-1][k] : 0))。
    • 再尝试用失配：
      有两种用失配的方式：
      a) 失配用在当前字符 ')' 上：那么当前字符是失配，所以长度可以从 dp[i-1][0] + 1 来，且 k 从 0 变 1：
      dp[i][1] = max(dp[i][1], dp[i-1][0] + 1)。
      b) 失配用在前面匹配的左括号上（即 s[j] 是失配）：
      这需要更细致的处理，但我们可以通过另一种思路简化：

步骤 5：更简单的思路——两次扫描的贪心扩展

经典“最长有效括号子串”问题可以用两次扫描（从左到右、从右到左）的贪心法解决。
允许一次失配时，我们可以枚举失配位置，然后分别计算左右两边的有效长度，再相加。

具体：

  1. 枚举失配位置 m（0 ≤ m < n），将 s[m] 视为失配字符（即忽略它）。
  2. 在 s[0..m-1] 和 s[m+1..n-1] 这两段中，分别用经典无失配的方法计算最长有效括号子串长度，但必须注意它们必须分别以 m-1 结尾和以 m+1 开头吗？不一定，因为失配字符在中间，两段是独立的。
  3. 但这种方法会变成 O(n²)，因为对每个 m 要 O(n) 扫描。

步骤 6：最终采用的 DP 方案

经过权衡，这里给出一个 O(n) 的动态规划解法，状态增加一维记录失配次数：

定义：
dp[i][k] 表示以 i 结尾，使用了 k 次失配（k=0 或 1）的有效括号子串长度。若无法形成有效子串则为 0。

转移：

  1. 如果 s[i] = '('：
    • dp[i][0] = 0（无失配时，'(' 不能作为有效子串结尾）。
    • dp[i][1] = max(dp[i][1], (i > 0 ? dp[i-1][0] : 0) + 1)（将当前 '(' 视为失配，长度+1）。
  2. 如果 s[i] = ')'：
    • 先尝试匹配 s[i-1] = '('：
      • 如果 i >= 1 且 s[i-1] = '('：
        dp[i][k] = max(dp[i][k], (i >= 2 ? dp[i-2][k] : 0) + 2)。
    • 再尝试匹配更前面的 '('：
      • 令 j = i - dp[i-1][k] - 1，如果 j >= 0 且 s[j] = '('：
        dp[i][k] = max(dp[i][k], dp[i-1][k] + 2 + (j >= 1 ? dp[j-1][k] : 0))。
    • 尝试使用失配：
      • 将当前 ')' 视为失配：dp[i][1] = max(dp[i][1], (i > 0 ? dp[i-1][0] : 0) + 1)。
      • 将匹配的左括号视为失配：这在上面的“j”情况中，如果 k=0，我们可以让 s[j] 失配，即用 dp[i-1][0] 和 dp[j-1][0] 来更新 dp[i][1]，但需确保 j 是 '('。
        具体：如果 j >= 0 且 s[j] = '(' 且 k=0，则：
        dp[i][1] = max(dp[i][1], dp[i-1][0] + 2 + (j >= 1 ? dp[j-1][0] : 0))。

初始化：dp[i][k] = 0。
最终答案：max(dp[i][0], dp[i][1]) 对所有 i 取最大值。

步骤 7：示例推演

以 s = "())" 为例，n=3：
初始化全 0。

i=0: '('
dp[0][0]=0, dp[0][1] = dp[-1][0]+1 不存在，所以为 0。

i=1: ')'
匹配 s[0]='('：
dp[1][0] = dp[-1][0]+2 = 2。
尝试用失配：当前 ')' 失配：dp[1][1] = dp[0][0]+1 = 1。
所以 dp[1][0]=2, dp[1][1]=1。

i=2: ')'
先尝试匹配 s[1]=')'：
j = 2 - dp[1][0] - 1 = 2 - 2 - 1 = -1，无效。
尝试用失配：当前 ')' 失配：dp[2][1] = dp[1][0]+1 = 3。
另外匹配更前面的 '('：用 k=1 试试：
j = 2 - dp[1][1] - 1 = 2 - 1 - 1 = 0，s[0]='('，所以：
dp[2][1] = max(3, dp[1][1]+2+dp[-1][1]) = max(3, 1+2+0) = 3。
所以 dp[2][0]=0, dp[2][1]=3。

最终答案 max=3，匹配示例输出。

总结

这个问题的核心在于在经典有效括号子串 DP 上增加一个“失配次数”的状态维度，并在遇到 '(' 或 ')' 时，分别考虑是否将该字符作为失配字符，以及是否在匹配过程中消耗一次失配。
通过合理分类讨论，可以在 O(n) 时间内求解。

最长有效括号匹配子串的变种——允许一次失配的最长有效括号子串 题目描述 给定一个只包含 '(' 和 ')' 的字符串 s ，找出其中最长的有效括号 子串 的长度，但允许 最多一次 “失配”（即允许有一个位置的括号不匹配，但整个子串在允许一次失配的前提下，其余括号必须能完全匹配）。 有效括号匹配的定义是：每个 '(' 都有一个对应的 ')' 与之正确配对，并且括号顺序正确。 示例 输入： s = "(()" 输出： 2 解释： "()" 是有效子串，但允许一次失配时，整个字符串 "(()" 如果允许第一个 '(' 失配（即不参与匹配），则 "()" 是有效的，长度为 2。 输入： s = "())" 输出： 3 解释：整个字符串 "())" 允许最后一个 ')' 失配，前两个字符 "()" 有效，整体视为允许一次失配的有效子串，长度为 3。 输入： s = ")(()" 输出： 2 解释：子串 "()" 是有效的，且没有失配，长度为 2。 解题过程循序渐进讲解 步骤 1：回顾经典问题（最长有效括号子串，无失配） 经典的动态规划解法定义： dp[i] 表示以 s[i] 结尾的最长有效括号子串长度。 转移方程： 如果 s[i] = ')' ： 如果 s[i-1] = '(' ，则 dp[i] = dp[i-2] + 2 （匹配一对括号，加上前面的有效长度）。 如果 s[i-1] = ')' 且 s[i - dp[i-1] - 1] = '(' ，则 dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2] （跨越中间已匹配的部分，匹配更前面的一对括号）。 最终答案是 max(dp[i]) 。 步骤 2：扩展思路，允许一次失配 我们可以在经典动态规划的基础上增加一个维度，表示“已使用的失配次数”。 定义状态： dp[i][k] 表示以 s[i] 结尾、且 使用了 k 次失配 （k = 0 或 1）的最长有效括号子串长度。 注意：这里的“有效”是 在允许 k 次失配的前提下，其余括号完全匹配 。 关键：如何定义“失配”？ 在括号匹配中，失配可以出现在两个位置： 当前位置的字符“应该匹配”但故意让它不匹配（即不参与任何配对）。 在匹配过程中，允许一个多余的左括号或右括号不参与匹配，但整个序列仍能在允许一次失配的条件下视为“有效”。 更精确地说：我们允许在 整个子串 中，最多有一个括号是“多余的”或“缺失的”（即无法找到匹配的对应括号），但其他括号必须完全匹配。 步骤 3：转移方程推导 我们分情况考虑 s[i] 的取值和已用失配次数 k。 情况 1： s[i] = '(' 如果 k = 0（尚未使用失配）：以 '(' 结尾，且前面没有失配，这个 '(' 是新的左括号，暂时没有右括号匹配它。但我们可以 允许它成为一次失配 吗？ 如果允许它成为失配，则状态转移到 dp[i][1] 。但注意：如果我们让它失配，那么它就不参与匹配，子串长度只能从 dp[i-1][0] 继承，然后加 1（当前字符）。 所以： dp[i][1] = max(dp[i][1], dp[i-1][0] + 1) （将当前 '(' 视为失配字符）。 同时， dp[i][0] 无法更新，因为 '(' 结尾且无失配时，它没有右括号匹配，所以 dp[i][0] = 0 （除非前面有某种方式让它匹配，但不可能，因为 '(' 必须在后面有 ')' 匹配，这里只考虑以 i 结尾的子串）。 如果 k = 1（已用过一次失配）：当前 '(' 不能作为失配字符（因为已用过一次失配），且它没有匹配的右括号，所以 dp[i][1] = 0 （以 '(' 结尾且已用过失配，无法形成有效子串）。 但注意：有一种特殊情况，即前面的子串允许一次失配，当前 '(' 是正常的左括号，它可能需要等待后面的 ')' 来匹配，但这是以 i 结尾的子串，所以如果当前字符是 '(' ，它无法完成匹配，所以 dp 为 0，除非我们考虑更复杂的“等待匹配”状态，但这会使问题复杂化。 为了简化，我们可以 只考虑有效子串必须是以合法匹配结束 ，即最后一个字符必须是匹配成功的右括号（除了允许的一次失配可以在任意位置）。 这样会导致：如果当前字符是 '(' ，那么以它结尾的子串 不可能 是“完全匹配（允许一次失配）”的，除非这个 '(' 本身就是那个失配字符。 所以我们只允许在 k=0 时，将 '(' 视为失配字符，从而得到长度。 情况 2： s[i] = ')' 这是可以完成匹配的字符，分两种子情况： 子情况 2.1： s[i-1] = '(' （即形如 "()" ） 如果 k=0：那么这对括号匹配，长度是 2，再加上前面以 i-2 结尾的最长有效子串长度（无失配）： dp[i][0] = dp[i-2][0] + 2 。 如果 k=1： 此时已用过一次失配，这对括号可以匹配，但失配可能出现在前面某个位置。 所以： dp[i][1] = dp[i-2][1] + 2 （失配已用在前面的某处）。 另外，还有一种可能：失配用在这个 '(' 上，即这个 '(' 是失配字符，那么当前 ')' 无法匹配，这种情况实际上不可能形成以 i 结尾的有效子串（因为右括号无匹配）。 所以不考虑。 子情况 2.2： s[i-1] = ')' （即形如 "...))" ） 设 j = i - dp[i-1][k'] - 1 ，其中 k' 是前面用过的失配次数。我们需要考虑前面已匹配的一段，再往前看一个字符是否能与当前 ')' 匹配。 经典无失配的公式是：如果 s[j] = '(' ，则 dp[i] = dp[i-1] + 2 + dp[j-1] 。 现在带失配，我们分几种小情况： (a) 不失配，正常匹配 即 s[j] = '(' ，且 k = k'（即失配次数不变），则： dp[i][k] = max(dp[i][k], dp[i-1][k] + 2 + dp[j-1][k]) 。 (b) 将 s[ j] 视为失配字符 前提是 k' = 0，且我们让 s[ j ] 失配，则 k 变成 1。 这样 s[ j] 是 '(' 但它不参与匹配，那么当前 ')' 必须与更前面的 '(' 匹配，这需要 j 前面的有效子串，并且 s[ j-1] 必须是与当前 ')' 匹配的左括号，但这样会复杂化。 实际上更简单的方法是：将失配字符的“角色”放在当前子串的任意一个位置，而不一定是 s[ j ]。 步骤 4：简化状态定义 为了避免复杂讨论，我们可以这样设计状态： dp[i][k] 表示以 s[i] 结尾、且 允许 k 次失配 （k=0 或 1）的 最长有效括号子串长度 。 这里的“有效”是指：除去最多 k 个失配字符，剩下的括号序列完全匹配。 这样，我们可以用类似经典 DP 的思路，但允许在匹配过程中“跳过”一个字符（即视它为失配）。 转移方程（更系统化） ： 如果 s[i] = '(' ： 不使用失配： dp[i][0] = 0 （因为 '(' 无法作为结尾完成匹配）。 使用一次失配： dp[i][1] = max(dp[i][1], dp[i-1][0] + 1) （将当前 '(' 当作失配字符，所以长度+1，失配次数从0变1）。 如果 s[i] = ')' ： 先尝试正常匹配（不失配）： 如果 s[i-1] = '(' ： dp[i][k] = dp[i-2][k] + 2 （k=0 或 1）。 否则（ s[i-1] = ')' ）：令 j = i - dp[i-1][k] - 1 ，如果 j >= 0 且 s[j] = '(' ，则 dp[i][k] = max(dp[i][k], dp[i-1][k] + 2 + (j-1 >= 0 ? dp[j-1][k] : 0)) 。 再尝试用失配： 有两种用失配的方式： a) 失配用在当前字符 ')' 上：那么当前字符是失配，所以长度可以从 dp[i-1][0] + 1 来，且 k 从 0 变 1： dp[i][1] = max(dp[i][1], dp[i-1][0] + 1) 。 b) 失配用在前面匹配的左括号上（即 s[ j ] 是失配）： 这需要更细致的处理，但我们可以通过另一种思路简化： 步骤 5：更简单的思路——两次扫描的贪心扩展 经典“最长有效括号子串”问题可以用两次扫描（从左到右、从右到左）的贪心法解决。 允许一次失配时，我们可以 枚举失配位置 ，然后分别计算左右两边的有效长度，再相加。 具体： 枚举失配位置 m （0 ≤ m < n），将 s[ m ] 视为失配字符（即忽略它）。 在 s[ 0..m-1] 和 s[ m+1..n-1 ] 这两段中，分别用经典无失配的方法计算最长有效括号子串长度，但必须注意它们必须分别以 m-1 结尾和以 m+1 开头吗？不一定，因为失配字符在中间，两段是独立的。 但这种方法会变成 O(n²)，因为对每个 m 要 O(n) 扫描。 步骤 6：最终采用的 DP 方案 经过权衡，这里给出一个 O(n) 的动态规划解法，状态增加一维记录失配次数： 定义： dp[i][k] 表示以 i 结尾，使用了 k 次失配（k=0 或 1）的 有效括号子串 长度。若无法形成有效子串则为 0。 转移： 如果 s[i] = '(' ： dp[i][0] = 0 （无失配时，'(' 不能作为有效子串结尾）。 dp[i][1] = max(dp[i][1], (i > 0 ? dp[i-1][0] : 0) + 1) （将当前 '(' 视为失配，长度+1）。 如果 s[i] = ')' ： 先尝试匹配 s[ i-1 ] = '('： 如果 i >= 1 且 s[ i-1 ] = '('： dp[i][k] = max(dp[i][k], (i >= 2 ? dp[i-2][k] : 0) + 2) 。 再尝试匹配更前面的 '('： 令 j = i - dp[i-1][k] - 1 ，如果 j >= 0 且 s[ j ] = '('： dp[i][k] = max(dp[i][k], dp[i-1][k] + 2 + (j >= 1 ? dp[j-1][k] : 0)) 。 尝试使用失配： 将当前 ')' 视为失配： dp[i][1] = max(dp[i][1], (i > 0 ? dp[i-1][0] : 0) + 1) 。 将匹配的左括号视为失配：这在上面的“j”情况中，如果 k=0，我们可以让 s[ j] 失配，即用 dp[ i-1][ 0] 和 dp[ j-1][ 0] 来更新 dp[ i][ 1 ]，但需确保 j 是 '('。 具体：如果 j >= 0 且 s[ j ] = '(' 且 k=0，则： dp[i][1] = max(dp[i][1], dp[i-1][0] + 2 + (j >= 1 ? dp[j-1][0] : 0)) 。 初始化： dp[i][k] = 0 。 最终答案： max(dp[i][0], dp[i][1]) 对所有 i 取最大值。 步骤 7：示例推演 以 s = "())" 为例，n=3： 初始化全 0。 i=0: '(' dp[ 0][ 0]=0, dp[ 0][ 1] = dp[ -1][ 0 ]+1 不存在，所以为 0。 i=1: ')' 匹配 s[ 0 ]='('： dp[ 1][ 0] = dp[ -1][ 0 ]+2 = 2。 尝试用失配：当前 ')' 失配：dp[ 1][ 1] = dp[ 0][ 0 ]+1 = 1。 所以 dp[ 1][ 0]=2, dp[ 1][ 1 ]=1。 i=2: ')' 先尝试匹配 s[ 1 ]=')'： j = 2 - dp[ 1][ 0 ] - 1 = 2 - 2 - 1 = -1，无效。 尝试用失配：当前 ')' 失配：dp[ 2][ 1] = dp[ 1][ 0 ]+1 = 3。 另外匹配更前面的 '('：用 k=1 试试： j = 2 - dp[ 1][ 1] - 1 = 2 - 1 - 1 = 0，s[ 0 ]='('，所以： dp[ 2][ 1] = max(3, dp[ 1][ 1]+2+dp[ -1][ 1 ]) = max(3, 1+2+0) = 3。 所以 dp[ 2][ 0]=0, dp[ 2][ 1 ]=3。 最终答案 max=3，匹配示例输出。 总结 这个问题的核心在于在经典有效括号子串 DP 上增加一个“失配次数”的状态维度，并在遇到 '(' 或 ')' 时，分别考虑是否将该字符作为失配字符，以及是否在匹配过程中消耗一次失配。 通过合理分类讨论，可以在 O(n) 时间内求解。