My O(N) time C++ solutions: stack based and  DP based
DP based solution, O(N) time O(N) space\n\nWe can do DP: dp[i] saves the longest valid parentheses that ends at (i-1). To calculate the longest valid parenthese
 - DP based solution, O(N) time O(N) space\n\nWe 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\n1) case 1: s[i] = '(', then no valid parentheses that ends at i, so dp[i+1]=0 (i.e. do nothing)\n2) 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] = '('); \nif 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]  \nif no, then no valid parentheses ending at i, so dp[i+1] =0 (do nothing)\n\n    class Solution {\n    public:\n        int longestValidParentheses(string s) {\n            int len = s.size(), i, res=0, left;\n            vector<int> dp(len+1,0);\n            \n            for(i=1;i<len;++i)\n            {\n                if(s[i]==')')\n                {\n                    left = i-dp[i]-1;\n                    if(left>=0 && s[left]=='(') dp[i+1] = dp[i]+2+dp[left];\n                    res = max(res, dp[i+1]);\n                }\n            }\n            return res;\n            \n        }\n    };\n\n 2)  Stack based solution, O(N) time and O(N) space\nScan 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.\n\n    class Solution {\n    public:\n        int longestValidParentheses(string s) {\n            int len = s.size(), maxL=0, i;\n            stack<int> stk;\n            stk.push(-1);\n            for(i=0; i<len;++i)\n            {\n                if(s[i]==')' && stk.top()>=0 && s[stk.top()]=='(')\n                { // if s[i] is ')' and matches the last unmatched  char  \n                    stk.pop(); // remove the last unmatched char\n                    maxL = max(maxL, i-stk.top()); // update res\n                }\n                else stk.push(i);\n            }\n            return maxL;\n        }\n    };
[]