# 32. Longest Valid Parentheses

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

Example 1:

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

Example 2:

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

``````class Solution {
public:
int longestValidParentheses(string s) {
int res = 0, start = 0, n = s.size();
stack<int> st;
for (int i = 0; i < n; ++i) {
if (s[i] == '(') st.push(i);
else if (s[i] == ')') {
if (st.empty()) start = i + 1;
else {
st.pop();
res = st.empty() ? max(res, i - start + 1) : max(res, i - st.top());
}
}
}
return res;
}
};
``````

**

``````class Solution {
public:
int longestValidParentheses(string s) {
int res = 0, n = s.size();
vector<int> dp(n + 1);
for (int i = 1; i <= n; ++i) {
int j = i - 2 - dp[i - 1];
if (s[i - 1] == '(' || j < 0 || s[j] == ')') {
dp[i] = 0;
} else {
dp[i] = dp[i - 1] + 2 + dp[j];
res = max(res, dp[i]);
}
}
return res;
}
};
``````

``````class Solution {
public:
int longestValidParentheses(string s) {
int res = 0, left = 0, right = 0, n = s.size();
for (int i = 0; i < n; ++i) {
(s[i] == '(') ? ++left : ++right;
if (left == right) res = max(res, 2 * right);
else if (right > left) left = right = 0;
}
left = right = 0;
for (int i = n - 1; i >= 0; --i) {
(s[i] == '(') ? ++left : ++right;
if (left == right) res = max(res, 2 * left);
else if (left > right) left = right = 0;
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/32

Remove Invalid Parentheses

Generate Parentheses

Valid Parentheses

https://leetcode.com/problems/longest-valid-parentheses/

https://bangbingsyb.blogspot.com/2014/11/leetcode-longest-valid-parentheses.html

https://leetcode.com/problems/longest-valid-parentheses/discuss/14126/My-O(n)-solution-using-a-stack

https://leetcode.com/problems/longest-valid-parentheses/discuss/14133/My-DP-O(n)-solution-without-using-stack

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation