My short python solution using stack in O(n)

  • 0
    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'))
                    if not stack or stack[-1][1] == 'r':
                        stack.append((i, 'r'))
                        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.