# My O(N) time C++ solutions: stack based and DP based

• DP based solution, O(N) time O(N) space

We can do DP: dp[i] saves the longest valid parentheses that ends at (i-1). To calculate the longest valid parentheses that ends at i (i.e. calculate dp[i+1]), we only need to consider the following cases

1. case 1: s[i] = '(', then no valid parentheses that ends at i, so dp[i+1]=0 (i.e. do nothing)

2. case 2 s[i]= ')' , then we have to check if this ')' can find a matched '(' just before the longest parentheses ending at i-1 (i.e. check if s[i-dp[i]-1] = '(');
if yes, then s[i] extends the longest parentheses ending at i-1 to [i-dp[i]-1, i] and it now connects to the longest parentheses ending at i-dp[i]-2, so the DP update equation becomes dp[i+1] =dp[i]+2+dp[i-dp[i]-1]
if no, then no valid parentheses ending at i, so dp[i+1] =0 (do nothing)

class Solution {
public:
int longestValidParentheses(string s) {
int len = s.size(), i, res=0, left;
vector<int> dp(len+1,0);

``````     for(i=1;i<len;++i)
{
if(s[i]==')')
{
left = i-dp[i]-1;
if(left>=0 && s[left]=='(') dp[i+1] = dp[i]+2+dp[left];
res = max(res, dp[i+1]);
}
}
return res;

}
``````

};

3. Stack based solution, O(N) time and O(N) space
Scan s from left to right and use a stack to save all the unmatched '(' or ')' indices. If s[i] ='(', then push i to the stack; if s[i] =')', check if it can match the last unmatched char (i.e. check if s[stk.top()]='('), if so, remove tthe top entry and update res if the current parentheses [stk.top(), i] is longer than res.

``````class Solution {
public:
int longestValidParentheses(string s) {
int len = s.size(), maxL=0, i;
stack<int> stk;
stk.push(-1);
for(i=0; i<len;++i)
{
if(s[i]==')' && stk.top()>=0 && s[stk.top()]=='(')
{ // if s[i] is ')' and matches the last unmatched  char
stk.pop(); // remove the last unmatched char
maxL = max(maxL, i-stk.top()); // update res
}
else stk.push(i);
}
return maxL;
}
};``````

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