# 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.
# Code (Python)
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;
}
};