O(1)place,O(n)time,without stack


  • 0
    J
    class Solution(object):
        def longestValidParentheses(self, s):
            left=right=0
            length_left=0
            length_right=0
            index=-1
            for i,p in enumerate(s):
                if p =='(':
                    left+=1
                else:
                    right+=1
                if left<right:
                    length_left=max(length_left,left*2)
                    left=right=0
                    index=i
            if left==right:
                length_right=max(length_right,left*2)
            left = right = 0
            for i,p in enumerate(s[::-1]):
                if i == len(s)-index-1:
                    break
                if p==')':
                    right+=1
                else:
                    left+=1
                if left>right:
                    length_right=max(length_right,right*2)
                    left=right=0
            if left==right:
                length_right=max(length_right,left*2)
            return max(length_left,length_right)
    

Log in to reply
 

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