Official 719 views

Editorial: Longest Valid Parentheses

by admin · Oct. 18, 2026

1 Intuition

Keep the index just before the current valid run at the bottom of a stack.

2 Approach

Push indices of '('. On ')', pop; if the stack empties, this ')' becomes the new boundary, otherwise the valid length is i − top.

3 Complexity Analysis

Time O(n), Space O(n).

4 Solution Code

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack, best = [-1], 0
        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    best = max(best, i - stack[-1])
        return best

5 Code Walkthrough

The reference solution below implements the approach step by step.