## # 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 "()()"
``````

### # Solution

Approach 1: Stack.

Approach 2: DP.

Approach 3: Traverse from left to right and then from right to left.

Approach 1:

Approach 2:

Approach 3:

### # Code (C++)

Approach 1:

``````// Stack.
// Need to use stack, since we need to distinguish, e.g., "()(()" and "(()()".
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> st;
for (int i = 0; i < s.size(); ++i)
{
if (s[i] == ')' && !st.empty() && s[st.top()] == '(')
st.pop();
else
st.push(i);
}
int prev = s.size();
int maxLen = 0;
while (!st.empty())
{
maxLen = std::max(maxLen, prev - st.top() - 1);
prev = st.top();
st.pop();
}
maxLen = std::max(maxLen, prev);
return maxLen;
}
};
``````

Approach 2:

``````// DP.
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
if (n == 0)
return 0;
vector<int> len(n, 0); // the length of the longest valid string ends with s[i]
int maxLen = 0;
for (int i = 1; i < n; ++i)
{
if (s[i] == ')')
{
int j = i - 1 - len[i-1];
if (j >= 0 && s[j] == '(')
{
len[i] = len[i-1] + 2;
if (j - 1 >= 0)
len[i] += len[j-1];
maxLen = std::max(maxLen, len[i]);
}
}
}
return maxLen;
}
};
``````

Approach 3:

``````// Traverse from left to right and then from right to left.
class Solution {
public:
int longestValidParentheses(string s) {
int left = 0;
int right = 0;
int maxLen = 0;
for (int i = 0; i < s.size(); ++i)
{
if (s[i] == '(')
left++;
else
right++;
if (left == right)
maxLen = std::max(maxLen, right * 2);
else if (right > left)
{
left = 0;
right = 0;
}
}
left = 0;
right = 0;
for (int i = s.size() - 1; i >= 0; --i)
{
if (s[i] == '(')
left++;
else
right++;
if (left == right)
maxLen = std::max(maxLen, right * 2);
else if (left > right) // not "else if (right > left)".
{
left = 0;
right = 0;
}
}
return maxLen;
}
};
``````