# LeetCode Longest Valid Parentheses

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 n = s.size(), maxval = 0;
for (int i = 0; i < n; i++) { if (s[i] == ‘(‘) {
stack<char> sc;
sc.push(s[i]);
int cur = 0;
for (int j = i + 1; j < n; j++) {
char t = sc.top();
if (s[j] == ‘)’)
{ if (t == ‘(‘) {
sc.pop();
cur++; } else break;
}
sc.push(s[j]);
}
if (cur > maxval)
maxval = cur; }
}
return maxval * 2;
}
};

class Solution {
public:
int longestValidParentheses(string s)
{
int n = s.size(), maxval = 0, start = -1; // start初始化为-1
stack<int> si;
for (int i = 0; i < n; i++) {
if (s[i] == '(') {
si.push(i); //左括号无条件压栈
} else { //右括号不压栈
if (si.empty()) {
start = i; //以右括号作为新的起点
} else {
si.pop();
if (si.empty()) // ()()() or (()())
maxval = max(maxval, i - start);
else // (() 用当前栈顶索引作为起点
maxval = max(maxval, i - si.top());
}
}
}
return maxval;
}
};

(((() ^ ^

xxx((xxxx))

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

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