My solution with two stacks, want to share it.

• ``````class Solution {
public:
int longestValidParentheses(string s) {
/* idea: use two stack
* stack 'left' stores '(' which are not macthed
* stack 'right' stores the index of each macthed ')' as well as the number of pathrenthess it could match
*/
if(s.length() < 2)
return 0;

stack<int> left;
stack<pair<int, int> > right;
for(unsigned int i = 0; i < s.length(); ++i){
if (s[i] == '('){
left.push(i);
}else{
if(!left.empty()){
int top = left.top();
left.pop();
while(!right.empty() && right.top().first > top)
right.pop();
int matchLen = i - top + 1;
if(!right.empty() && right.top().first + 1 == top){
matchLen += right.top().second;
right.pop();
right.push(make_pair(i, matchLen));
}else{
right.push(make_pair(i, matchLen));
}
}
}
}
int maxLen = 0;
while(!right.empty()){
maxLen = max(maxLen, right.top().second);
right.pop();
}
return maxLen;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.