32. Longest Valid Parentheses

Solution 1: Stack

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        ans = 0
        stack = []
        startIdxOfLastValidPair = 0
        for idx in range(len(s)):
            if s[idx] == '(':
                stack.append(idx)
            # s[idx] == ')' and Stack empty
            elif not stack:
                startIdxOfLastValidPair = idx + 1 # e.g, ')()'
            # s[idx] == ')' and Stack has idx of previous '('
            else:
                stack.pop()

                # e.g, '...()()()()...', continuously update ans
                if not stack:
                    ans = max(ans, idx - startIdxOfLastValidPair + 1)
                # e.g, '...(()()...'
                else:
                    ans = max(ans, idx - stack[-1])
        return ans

Time Complexity: O(N)
Space Complexity: O(N)

Solution 2: DP

Time Complexity: O(N)
Space Complexity: O(N)

Solution 3: Two Pointer

Time Complexity: O(N)
Space Complexity: O(1)

Reference

https://www.cnblogs.com/grandyang/p/4424731.html

Follow-up: Valid Parentheses