October 3Hard

Longest valid parentheses

String
Dynamic Programming
Stack
Bracket Sequences

Problem

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

Solution

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        end = [-1] * n
        stack = []
        for i in range(n):
            if s[i] == ")":
                if stack:
                    j = stack.pop()
                    end[j] = i
            else:
                stack.append(i)
        max_len = 0
        curr_len = 0
        i = 0
        while i < n:
            if end[i] != -1:
                j = end[i]
                curr_len += j - i + 1
                i = j
            else:
                max_len = max(max_len, curr_len)
                curr_len = 0
            i += 1
        max_len = max(max_len, curr_len)

        return max_len