Constant space, O(n) time with forward and backward pass
When right parentheses are more than left parentheses in the forward pass, we can discard previous parentheses. In the backward pass, when left parentheses are 
When right parentheses are more than left parentheses in the forward pass, we can discard previous parentheses. In the backward pass, when left parentheses are more than right parentheses, we can discard previous parentheses. \n\n\n    int longestValidParentheses(string s) {\n        int longest = 0;\n        int extra=0;\n        int length=0;\n        for(int i=0; i<s.size(); i++) {\n            if(s[i] == '(') {\n                extra++;\n                length++;\n            }\n            else {\n                if(extra>0) {\n                    extra--;\n                    length++;\n                    if(extra == 0)\n                        longest = max(longest, length);\n                }\n                else {\n                    extra = 0;\n                    length=0;\n                }\n            }\n        }\n        length = 0;\n        extra=0;\n        for(int i=s.size()-1; i>=0; i--) {\n            if(s[i] == ')') {\n                extra++;\n                length++;\n            }\n            else {\n                if(extra>0){\n                    extra--;\n                    length++;\n                    if(extra == 0)\n                        longest = max(longest, length);\n                    \n                }\n                else {\n                    extra = 0;\n                    length=0;\n                }\n            }\n        }\n        return longest;\n    }
[]