What is the main idea behind the DP approach for Longest Valid Parentheses?

The DP approach stores the length of the longest valid substring ending at each index, updating when a closing parenthesis matches an opening one, efficiently accumulating nested or consecutive valid lengths.

How does the stack-based method handle unmatched parentheses?

The stack keeps indices of unmatched opening parentheses, and a base index tracks unmatched closing ones. Popping and length calculations occur only when a matching closing parenthesis is found, ensuring accurate maximum lengths.

Why perform two passes with counters in this problem?

Two linear scans, left-to-right and right-to-left, allow counting matched pairs while resetting counters when mismatches occur, ensuring that edge cases with unmatched starting or trailing parentheses are correctly measured.

Can this problem be solved with O(1) extra space?

Yes, using the two-pass counter method requires only a few integer counters, achieving O(1) space while still accurately computing the maximum length of valid parentheses substrings.

What is a common mistake when implementing state transition DP here?

A frequent error is failing to reference the DP entry before the matching opening parenthesis correctly, which undercounts nested or consecutive valid sequences, leading to incorrect maximum length results.

#32

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())" 。示例 1：输入： s = "(()" 输出： 2 解释：最长有效括号子串是 "()" 示例 2： …

字符串动态规划栈

题目描述

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

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

提示：

0 <= s.length <= 3 * 10⁴
s[i] 为 '(' 或 ')'

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i]$ 表示以 $s[i-1]$ 结尾的最长有效括号的长度，那么答案就是 $\max\limits_{i=1}^n f[i]$ 。

如果 $s[i-1]$ 是左括号，那么以 $s[i-1]$ 结尾的最长有效括号的长度一定为 $0$ ，因此 $f[i] = 0$ 。
如果 $s[i-1]$ $s [i - 1]$ 是右括号，有以下两种情况：
- 如果 $s[i-2]$ 是左括号，那么以 $s[i-1]$ 结尾的最长有效括号的长度为 $f[i-2] + 2$ 。
- 如果 $s[i-2]$ 是右括号，那么以 $s[i-1]$ 结尾的最长有效括号的长度为 $f[i-1] + 2$ ，但是还需要考虑 $s[i-f[i-1]-2]$ 是否是左括号，如果是左括号，那么以 $s[i-1]$ 结尾的最长有效括号的长度为 $f[i-1] + 2 + f[i-f[i-1]-2]$ 。

因此，我们可以得到状态转移方程：

\begin{cases} f[i] = 0, & \textit{if } s[i-1] = '(',\\ f[i] = f[i-2] + 2, & \textit{if } s[i-1] = ')' \textit{ and } s[i-2] = '(',\\ f[i] = f[i-1] + 2 + f[i-f[i-1]-2], & \textit{if } s[i-1] = ')' \textit{ and } s[i-2] = ')' \textit{ and } s[i-f[i-1]-2] = '(',\\ \end{cases}

最后返回 $\max\limits_{i=1}^n f[i]$ 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        f = [0] * (n + 1)
        for i, c in enumerate(s, 1):
            if c == ")":
                if i > 1 and s[i - 2] == "(":
                    f[i] = f[i - 2] + 2
                else:
                    j = i - f[i - 1] - 1
                    if j and s[j - 1] == "(":
                        f[i] = f[i - 1] + 2 + f[j - 1]
        return max(f)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you correctly handle nested valid parentheses sequences with state transition logic?
question_mark
Can you optimize space usage by choosing between DP, stack, or two-counter scans?
question_mark
Will you update your DP or stack state properly when encountering consecutive valid pairs?

warning

常见陷阱

外企场景

error
Incorrectly counting overlapping or nested substrings, leading to underestimating maximum length.
error
Failing to handle unmatched closing parentheses, causing index errors or incorrect resets.
error
Using only one-directional scan without accounting for trailing unmatched opening parentheses.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the actual longest valid parentheses substring instead of just its length.
arrow_right_alt
Count the total number of distinct valid parentheses substrings in the string.
arrow_right_alt
Allow additional characters beyond '(' and ')', requiring filtering or adjusted DP rules.

help

常见问题

外企场景

继续练习

#488 祖玛游戏 #678 有效的括号字符串 #22 括号生成