My short python solution using stack in O(n)


  • 0
    G
    class Solution(object):
        def longestValidParentheses(self, s):
            """
            :type s: str
            :rtype: int
            """
            stack = []
            maxCnt = 0
            for i in xrange(len(s)):
                if s[i] == '(':
                    stack.append((i, 'l'))
                else:
                    if not stack or stack[-1][1] == 'r':
                        stack.append((i, 'r'))
                    else:
                        stack.pop()
                        maxCnt = max(maxCnt, i+1 if not stack else i-stack[-1][0])
            return maxCnt
    

    Key points:

    • We need to store the location as well as the type (left or right parenthesis) to calculate the length.

Log in to reply
 

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