2 passes without stack


  • 0
    Z
    class Solution(object):
        def longestValidParentheses(self, s):
            """
            :type s: str
            :rtype: int
            """
            left, right, longest = 0, 0, 0 
            
            for c in s:
                if c == '(':
                    left = left + 1
                else:
                    right = right + 1
                    
                if right == left:
                    longest = max(longest, left+right)
                    
                elif right > left:
                    left, right = 0, 0 
                    
            left, right = 0, 0 
            
            for c in reversed(s):
                if c == '(':
                    left = left + 1
                else:
                    right = right + 1
                    
                if right == left:
                    longest = max(longest, left + right)
                    
                elif left > right:
                    left, right = 0, 0 
                    
            return longest
    

    O(n) time and O(1) space, no stack needed
    However it only beats 30%. How can I improve it?


Log in to reply
 

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