# 32. Longest Valid Parentheses (H)

Given a string containing just the characters `'('` and `')'`, find the length of the longest valid (well-formed) parentheses substring.

 

**Example 1:**

```
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".
```

**Example 2:**

```
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".
```

**Example 3:**

```
Input: s = ""
Output: 0
```

 

**Constraints:**

* `0 <= s.length <= 3 * 104`
* `s[i]` is `'('`, or `')'`.

### Solution:

**Version 1: Stack**

1.遍历给字符串中的所有字符 1.1若当前字符s[index](https://www.jiuzhang.com/problem/longest-valid-parentheses/)为左括号'('，将当前字符下标index入栈（下标稍后有其他用处），处理下一字符 1.2若当前字符s[index](https://www.jiuzhang.com/problem/longest-valid-parentheses/)为右括号')'，判断当前栈是否为空 1.2.1若栈为空，则accumulatedLen = 0，当前有效长度为0，处理下一字符（当前字符右括号下标不入栈） 1.2.2若栈不为空，则出栈（由于仅左括号入栈，则出栈元素对应的字符一定为左括号，可与当前字符右括号配对），判断栈是否为空 1.2.2.1若栈为空，则maxlen = max(maxlen, index-start+1)，更新当前最大匹配序列长度 1.2.2.2若栈不为空，则maxlen = max(maxlen, i-栈顶元素值)，更新当前最大匹配序列长度

**Version2:  dp**

题解： 一般对于最长XX问题容易想到利用DP求解，在这题中利用逆向DP，设状态dp[i](https://www.jiuzhang.com/problem/longest-valid-parentheses/)为从i到len - 1中，以i开头的最长合法子串长度：

* 初始化：dp[len - 1](https://www.jiuzhang.com/problem/longest-valid-parentheses/) = 0
* 如果s[i](https://www.jiuzhang.com/problem/longest-valid-parentheses/) = ')'，则跳过，因为不可能有由'('开头的串
* 如果s[i](https://www.jiuzhang.com/problem/longest-valid-parentheses/) = '('，则需要找到右括号和它匹配，可以跳过以i + 1开头的合法子串，则需要看j = i + dp[i + 1](https://www.jiuzhang.com/problem/longest-valid-parentheses/) + 1是否为右括号。如果没越界且为右括号，那么有dp[i](https://www.jiuzhang.com/problem/longest-valid-parentheses/) = dp[i + 1](https://www.jiuzhang.com/problem/longest-valid-parentheses/) + 2，此外在这个基础上还要将j + 1开头的子串加进来（只要不越界）

**Version 3: Stack + dp**

如果你看过前文 [手把手解决三道括号相关的算法题](https://labuladong.github.io/article/?qno=20)，就知道一般判断括号串是否合法的算法如下：

```java
Stack<Integer> stk = new Stack<>();
for (int i = 0; i < s.length(); i++) {
    if (s.charAt(i) == '(') {
        // 遇到左括号，记录索引
        stk.push(i);
    } else {
        // 遇到右括号
        if (!stk.isEmpty()) {
            // 配对的左括号对应索引，[leftIndex, i] 是一个合法括号子串
            int leftIndex = stk.pop();
            // 这个合法括号子串的长度
            int len = 1 + i - leftIndex;
        } else {
            // 没有配对的左括号
        }
    }
}
```

但如果多个合法括号子串连在一起，会形成一个更长的合法括号子串，而上述算法无法适配这种情况。

所以需要一个 `dp` 数组，记录 `leftIndex` 相邻合法括号子串的长度，才能得出题目想要的正确结果。

```java
class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stk = new Stack<>();
        // dp[i] 的定义：记录以 s[i-1] 结尾的最长合法括号子串长度
        int[] dp = new int[s.length() + 1];
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                // 遇到左括号，记录索引
                stk.push(i);
                // 左括号不可能是合法括号子串的结尾
                dp[i + 1] = 0;
            } else {
                // 遇到右括号
                if (!stk.isEmpty()) {
                    // 配对的左括号对应索引
                    int leftIndex = stk.pop();
                    // 以这个右括号结尾的最长子串长度
                    int len = 1 + i - leftIndex + dp[leftIndex];
                    dp[i + 1] = len;
                } else {
                    // 没有配对的左括号
                    dp[i + 1] = 0;
                }
            }
        }
        // 计算最长子串的长度
        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/8.data-structure/32.-longest-valid-parentheses-h.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.