longestValidParentheses_linear.py

def longestValidParentheses(s: str) -> int:
    def scan(s: str, opening_char: str) -> int:
        longest = 0
        opened = 0
        start = 0
        for i in range(len(s)):
            if s[i] == opening_char:
                opened += 1
            elif opened > 0:
                opened -= 1
                if opened == 0:
                    longest = max(longest, i - start + 1)
            else:
                start = i + 1
        return longest

    return max(scan(s, '('), scan(s[::-1], ')'))