Easy O(n) with hash table, python


  • 0
    B

    The idea is , if we see a '(', we increase our count, and vise versa when we see a ').

    If, after a decrease, we see a number that happened before, we know there is a legal match.

    If count <0 we need to renew all the counts.

    class Solution(object):
        def longestValidParentheses(self, s):
            """
            :type s: str
            :rtype: int
            """
            Count=0
            Max=0
            
            Dic={}
            Dic[0]=0
            for i in range(1,len(s)+1):
                if s[i-1]=='(':
                    
                    Count+=1
                    Dic[Count]=i
                else:
                    Count-=1
                    
                    if Count >=0:
                        if Count in Dic:
                            Max=max(i-Dic[Count],Max)
                    elif Count<0:
                        Dic={}
                        Dic[0]=i
                        Count=0
            
            return Max
    

Log in to reply
 

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