O(n) Python, 96.55%, stack+dict, simple


  • 0
        def longestValidParentheses(self, s):
            parent_stack = []
            length_dict = {}
            
            for c in s:
                if c=='(':
                    parent_stack.append(c)
                else:
                    if c==')' and parent_stack and parent_stack[-1]=='(':
                        parent_stack.pop()
                        idx = len(parent_stack)-1
                        length_dict.setdefault(idx, 0)
                        length_dict[idx]+=length_dict.get(idx+1, 0)
                        length_dict[idx]+=2
                        length_dict[idx+1] = 0
                    else:
                        parent_stack.append(c)
                        
                        
            max_len = 0
            for k in length_dict:
                if length_dict[k]>max_len:
                    max_len = length_dict[k]
                    
            return max_len
    
    
    

Log in to reply
 

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