O(1) space python solution, no stack


  • 1

    scan s from left to right and then from right to left. The variable names are quite self-explaining.

    def longestValidParentheses(self, s):
        return max(self.helper(s,'('), self.helper(s[::-1],')'))
    
    def helper(self, s, left):
        ans = 0
        maxendinghere = 0
        count = 0
        for c in s:
            if c == left:    #when scan s from left to right, left is '(', otherwise is ')'
                count += 1
                maxendinghere += 1
            else: 
                count -= 1
                if count <0:
                    maxendinghere = 0
                    count = 0
                else:
                    maxendinghere += 1
                    if count == 0:
                        ans = max(ans, maxendinghere)
        return ans

Log in to reply
 

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