# Two solutions, one is based on stack, the other is memorization.

• The solution using stack is easy. Just try to keep the open (left) parentheses.

``````class Solution {
public:
int longestValidParentheses(string s) {
vector<int> stac;
stac.push_back(-1);
int size=s.length();
int res=0;
for(int i=0; i<size; ++i){
if(s[i]=='('){
stac.push_back(i);
}
else{
stac.pop_back();
if(!stac.empty()){
res=max(res, i-stac.back());
}
else{
stac.push_back(i);
}
}
}
return res;
}};
``````

But, by intuition, this kind of problem could be solved by DP, or memorization. Because there are a lot of duplicated checking if without memorization. Whenever you meet a ')', you need to:

1. look back one step to see if it's a '(',
2. Or, if it's a ')', jump back based on the memorized index to find another '('.
3. Add up previous valid parentheses.

Then we could have the following 8ms solution.

``````class Solution {
public:
int longestValidParentheses(string s) {
int size=s.length();
int res=0;
vector<int> d(size, 0);
for(int i=1; i<size; ++i){
if(s[i]==')'){
int prev=i-1-d[i-1];
if(prev>=0 && s[prev]=='('){
d[i]=d[i-1]+2;
if(prev>1){
d[i]=d[i]+d[prev-1];
}
res=max(res, d[i]);
}
}
}
return res;
}};``````

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