O(1) space python solution, no stack
scan s from left to right and then from right to left. The variable names are quite self-explaining. \n\n    def longestValidParentheses(self, s):\n        retu
scan s from left to right and then from right to left. The variable names are quite self-explaining. \n\n    def longestValidParentheses(self, s):\n        return max(self.helper(s,'('), self.helper(s[::-1],')'))\n    \n    def helper(self, s, left):\n        ans = 0\n        maxendinghere = 0\n        count = 0\n        for c in s:\n            if c == left:    #when scan s from left to right, left is '(', otherwise is ')'\n                count += 1\n                maxendinghere += 1\n            else: \n                count -= 1\n                if count <0:\n                    maxendinghere = 0\n                    count = 0\n                else:\n                    maxendinghere += 1\n                    if count == 0:\n                        ans = max(ans, maxendinghere)\n        return ans
[]