# LeetCode题目：Longest Valid Parentheses

By | 2012 年 9 月 30 日

Longest Valid Parentheses
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
For “(()”, the longest valid parentheses substring is “()”, which has length = 2.
Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

## code rewrite 2018-04-08 C++

```// for speeding up the execution
static const auto io_speed_up = []() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}();
class Solution {
public:
int longestValidParentheses(string s) {
int max_len = 0;

int * stack = new int[s.length() + 1];
int si = 0;
stack[0] = -1;

for(int i = 0; i < s.length(); i++) {
if( '(' == s[i] ) {
stack[++si] = i;
} else {
if( si > 0 ) {
--si;
int len = i - stack[si];
if( len > max_len ) max_len = len;
} else {
stack[0] = i;
}
}
}

return max_len;
}
};
```

## code rewrite 2018-04-08 C++

```class Solution {
public:
int longestValidParentheses(string s) {
int potential_left = -1; // the hard left boundery of potential valid substring
int max_len = 0;

std::stack<int> stack;
for(int i = 0; i < s.length(); i++) {
if( '(' == s[i] ) {
stack.push(i);
} else {
if( stack.size() > 0 ) {
stack.pop();
// if stack is not empty, then the top index in stack is the unpaired open parentheis after solve the ) at index i
// otherwise, the whole string (potential_left, i] is valid substring
int left = stack.size() == 0 ? potential_left : stack.top();
int len = i - left;
if( len > max_len )
max_len = len;
} else {
potential_left = i; //substring from this position can not be valid.
}
}
}

return max_len;
}
};
```

## code rewrite 2018-04-07 C++

```class Solution {
public:
int longestValidParentheses(string s) {
int len = 0; //tracking current length of valid substring
int prev_len = 0; //length of valid substring that possible to connect to the adjancent open parentheses
int max_len = 0;

std::stack<int> stack;
for(int i = 0; i < s.length(); i++) {
if( '(' == s[i] ) {
stack.push(prev_len);
stack.push(i);
prev_len = 0;
} else {
if( stack.size() > 0 ) {
int open_index = stack.top(); stack.pop();
int prev_len_connected = stack.top(); stack.pop();
len = i - open_index + 1 + prev_len_connected;
max_len = max_len >= len ? max_len : len;
prev_len = len;
} else {
prev_len = 0;
}
}
}

return max_len;
}
};
```

```struct Info{
int index;
int bonus;
};
class Solution {
public:
int longestValidParentheses(string s) {
vector ls;//left parentheses that not matched
int maxlen = 0;
int curBonus = 0;
for(int i = 0 ; i < s.size(); ++i) {
if(s[i] == '(') {
Info info;info.index = i;info.bonus = curBonus;
curBonus = 0;
ls.push_back(info);
} else {
curBonus = 0;
if(ls.size() > 0) {
Info lastleft = ls[ls.size() - 1];
ls.pop_back();
int len = i - lastleft.index + 1 + lastleft.bonus;
curBonus = len;
if(maxlen < len)
maxlen = len;
}
}
}
return maxlen;
}
};
```