Longest Valid Parentheses

def longest_valid_parentheses(s):
    dp = [0] * len(s)
    for i in range(1, len(s)):
        if s[i] == '(':
            continue
        if s[i - 1] == '(':
            before = dp[i - 2] if i >= 2 else 0
            dp[i] = before + 2
        else:
            j = i - dp[i - 1] - 1
            if j >= 0 and s[j] == '(':
                before = dp[j - 1] if j >= 1 else 0
                dp[i] = dp[i - 1] + 2 + before
    return max(dp, default=0)

Longest Valid Parentheses. Given a string of opens and closes, return the length of its longest well-formed substring. It builds on Valid Parentheses.

Open, open, close gives two. Close, open, close, open, close, close gives four: two pairs side by side. An empty string gives zero. And open, close, open, open, close, close is valid all the way: six.

The slow way: check every even-length substring with a counter. That's n squared substrings, each checked in linear time: n cubed.

The key idea: dp of i is the longest valid run ending at i. Only a close can end one. If an open sits right before it, they pair: two, plus the run before the pair. If a close sits there, jump back over that close's run. If an open waits just before it, add two, the inner run, and the run before that open.

In code, one pass fills dp from left to right, and the answer is the largest entry. A stack of indices also works in linear time.

Now close, open, close, open, close, close. The first close has nothing before it: zero. Opens always stay zero. The next close pairs with its open: two. The next one pairs too, and adds the two before it: four. The last close jumps back and finds a close, not an open: zero. The answer is four.

One pass: linear time. One entry per character: linear space.

Look back, pair up, add the run before. That's Longest Valid Parentheses.