32. Longest Valid Parentheses

Problem Link

Tutorial

Use a stack for the sequence. If it is a "(" push its index in. If it is a ")", check if the top element is a "(". If so pop it. Otherwise, push the ")" index in. After we walked through the whole sequence. The stack is a list of the indices of the illegal characters. We just go through it to find the longest gap between two neighbours.

Solution

class Solution(object):
    def longestValidParentheses(self, s):
    """
    :type s: str
    :rtype: int
    """
    stk = []
    for i, ch in enumerate(s):
        if ch == '(':
            stk.append(i)
        elif stk and s[stk[-1]] == '(':
            stk.pop()
        else:
            stk.append(i)
    stk.append(len(s))
    stk = [-1] + stk
    ret = 0
    for i in range(len(stk) - 1):
        ret = max(ret, stk[i + 1] - stk[i] - 1)
    return ret