Python O(n) solution with 2 passes sliding window, no stack or DP needed


  • 0
    Z
    class Solution(object):
        def longestValidParentheses(self, s):
            """
            :type s: str
            :rtype: int
            """
            longest = 0
            start = 0
            n = 0
            
            for i, p in enumerate(s):
                if p == "(":
                    n += 1
                else: # p == ")"
                    n -= 1
                
                if n < 0:
                    start = i + 1
                    n = 0
                elif n == 0:
                    longest = max(longest, i+1-start)
    
            start = 0
            n = 0
            for i, p in enumerate(s[::-1]):
                if p == "(":
                    n -= 1
                else: # p == ")"
                    n += 1
                
                if n < 0:
                    start = i + 1
                    n = 0
                elif n == 0:
                    longest = max(longest, i+1-start)
    
            return longest
    
    

Log in to reply
 

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