最长有效括号子串（Longest Valid Parentheses Substring）

我们来详细讲解如何求解最长有效括号子串问题。这是线性动态规划中的一个经典问题，它考察对字符串的遍历和状态转移的设计。

题目描述

给定一个只包含字符 ( 和 ) 的字符串 s，请你找出其中最长的有效（格式正确且连续）括号子串的长度。

有效括号子串定义：

1. 任何左括号 ( 必须有对应的右括号 ) 与之匹配。
2. 匹配的括号对必须连续且顺序正确，例如 "()" 有效，")( " 无效，"()( )" 是有效的但长度为 2（两个独立的有效对），而 "(())" 是长度为 4 的有效连续子串。

示例：

• 输入：s = "(()"
  输出：2（最长有效子串为 "()"）
• 输入：s = ")()())"
  输出：4（最长有效子串为 "()()"）
• 输入：s = ""
  输出：0

解题思路

这个问题可以使用动态规划解决，核心思路是：

• 定义 dp[i] 表示 以字符 s[i] 结尾的最长有效括号子串的长度。
• 我们只关心以 ) 结尾的位置，因为只有右括号才能与前面的左括号匹配形成有效对。
• 如果 s[i] == '('，则 dp[i] = 0，因为有效括号子串不可能以左括号结尾（它必须等待后续的右括号）。

步骤详解

步骤 1：定义状态

设 dp[i] 为以 s[i] 结尾的最长有效括号子串的长度。
初始化 dp 数组全为 0，长度为 n（字符串长度）。

步骤 2：状态转移方程

我们遍历 i 从 0 到 n-1：

情况 1：s[i] == '('
dp[i] = 0，因为有效子串不能以左括号结尾。

情况 2：s[i] == ')'
此时需要看前一个字符 s[i-1] 是什么。

1. 子情况 2.1：s[i-1] == '('
   此时 s[i-1] 和 s[i] 形成一对匹配的 ()。
   那么以 s[i] 结尾的最长有效子串长度至少为 2，并且还可以加上 s[i-2] 结尾的有效子串长度（如果存在的话）。
   因此：

\[ dp[i] = 2 + (dp[i-2] \ \text{如果} \ i \geq 2 \ \text{否则} \ 0) \]

2. 子情况 2.2：s[i-1] == ')'
   此时 s[i] 是右括号，且前面也是右括号。
   这表明可能存在嵌套的有效括号，比如 "((...))" 形式。
   设 j = i - dp[i-1] - 1，这个 j 表示与当前 s[i] 可能匹配的左括号的位置。
   解释：dp[i-1] 是以 s[i-1] 结尾的有效子串长度，那么从 i-1 往前跳 dp[i-1] 个字符，就到了这个有效子串的前一个字符（即位置 j）。
   如果 j >= 0 且 s[j] == '('，则 s[j] 和 s[i] 匹配。
   那么以 s[i] 结尾的有效子串长度为：

\[ dp[i] = dp[i-1] + 2 + (dp[j-1] \ \text{如果} \ j \geq 1 \ \text{否则} \ 0) \]

这里：

• dp[i-1] 是中间嵌套的有效长度。
• +2 是新匹配的一对 ( )。
• + dp[j-1] 是 j 前面可能存在的有效子串长度（拼接起来）。

步骤 3：举例推导

以 s = ")()())" 为例（索引从 0 开始）：

• i=0：)，s[-1] 不存在，dp[0]=0。
• i=1：(，dp[1]=0。
• i=2：)，s[1]=='('，属于子情况 2.1：
  dp[2] = 2 + dp[0] = 2 + 0 = 2。
• i=3：(，dp[3]=0。
• i=4：)，s[3]=='('，子情况 2.1：
  dp[4] = 2 + dp[2] = 2 + 2 = 4。
• i=5：)，s[4]==')'，子情况 2.2：
  j = i - dp[4] - 1 = 5 - 4 - 1 = 0，s[0]==')' 不是 (，所以不匹配，dp[5]=0。

最终 dp = [0,0,2,0,4,0]，最大值为 4，对应子串 "()()"。

步骤 4：算法实现

根据上述推导，我们可以写出代码：

def longestValidParentheses(s: str) -> int:
    n = len(s)
    if n == 0:
        return 0
    dp = [0] * n
    max_len = 0
    for i in range(1, n):
        if s[i] == ')':
            if s[i-1] == '(':
                dp[i] = 2 + (dp[i-2] if i >= 2 else 0)
            else:  # s[i-1] == ')'
                j = i - dp[i-1] - 1
                if j >= 0 and s[j] == '(':
                    dp[i] = dp[i-1] + 2 + (dp[j-1] if j >= 1 else 0)
            max_len = max(max_len, dp[i])
    return max_len

步骤 5：复杂度分析

• 时间复杂度：O(n)，只需一次遍历。
• 空间复杂度：O(n)，用于存储 dp 数组。

验证例子

1. 输入："(()"

   • i=0: ( → 0
   • i=1: ( → 0
   • i=2: )，s[1]=='(' → dp[2] = 2 + dp[0] = 2
     max_len = 2 ✅

2. 输入：")()())"
   如上推导，max_len = 4 ✅

3. 输入："()(())"

   • i=0: ( → 0
   • i=1: )，s[0]=='(' → dp[1] = 2
   • i=2: ( → 0
   • i=3: ( → 0
   • i=4: )，s[3]=='(' → dp[4] = 2 + dp[2] = 2
   • i=5: )，s[4]==')'，j = 5-2-1=2，s[2]=='(' → dp[5] = 2 + 2 + dp[1] = 6
     max_len = 6 ✅（整个字符串都是有效的）

关键点总结

• 核心是理解 dp[i] 的定义：以 s[i] 结尾的最长有效括号子串长度。
• 分类讨论当前字符是 ) 时的两种匹配情况：
  • 与前一个字符直接匹配成 ()。
  • 与前一个字符组成 )) 时，需要找到可能匹配的左括号位置 j。
• 注意边界条件（索引不要越界）。

这个解法是线性动态规划的典型应用，通过巧妙的状态转移，在 O(n) 时间内解决问题。