leetcode-stack

32. Longest Valid Parentheses.py

class Solution:
    """
    Greedy+stack:
    We use stack to keep track of index of unmatched parentheses.
    Top of stack is nearest index of unmatched parenthese.

    We traverse the given string forward.
        Initally, we put -1 in the stack.
        如果又括號就進stack, 左括號就出stack, 然後計算長度
        when encounter the open parenthese, we append the index
        when encounter the close parenthese, 
            stack.pop() # pop unmatched parentheses
            if stack is empty, it means there's no valid parentheses
                we append the index
            else:
                # the valid length is current idx - nearest index of unmatched parenthese
                length = idx - stack[-1]
    
    "()"
    stack=[-1]
    1-(-1) = 2
    Ref:
        https://www.youtube.com/watch?v=39CEPFCl5sE&ab_channel=LeetCode%E5%8A%9B%E6%89%A3
    """
    def longestValidParentheses(self, s: str) -> int:
        """
        Stack
        T:O(n)
        S:O(n)
        """
        n = len(s)
        if n <=1 :
            return 0
        stack = collections.deque([-1])
        max_len = 0
        for i in range(n):
            char = s[i]
            if char == "(":
                stack.append(i)
            elif char == ")":
                stack.pop()
                if len(stack) == 0:
                    stack.append(i)
                else:
                    # calculate length of valid parentheses
                    length = i - stack[-1]
                    max_len = max(max_len, length)
        return max_len