> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/8.data-structure/32.-longest-valid-parentheses-h.md).

# 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;
    }
}
```