Longest Valid Parentheses

Longest Valid Parentheses is a classic interview problem that looks like simple matching but hides a subtle twist: you have to measure the length of the longest correctly-matched run, not just check whether the whole string is balanced. A single stack of indices — seeded with a sentinel — does it in one pass.

The slow way first

You could try every substring, check each one for balance, and keep the longest valid length. There are O(n²) substrings and each check costs O(n), so that is O(n³) — hopeless for a long string.

The question to ask: as I scan left to right, can I always know where the current valid run started? If I track the index just before the current run, then whenever a ) closes a match I can compute the run length instantly by subtracting.

The idea: a stack of indices, seeded with -1

Push indices (not characters) onto a stack. Seed it with -1 as an imaginary boundary sitting just left of the string.

• On ( — push the index. It is an open paren waiting for a match.
• On ) — pop the top. If the stack is now empty, this ) matched nothing, so it becomes the new boundary: push its own index. If the stack is not empty, a valid run ends here; its length is i - stack[-1], and we update best.

The sentinel -1 is what makes the very first () measure to length 2 instead of needing a special case.

The key insight: the top of the stack is always the index just before the current valid run, so i - stack[-1] is exactly that run length.

Walk through it

Step through the animation on s = "()())". The pointer i scans left to right while the index stack fills and drains underneath. The first () measures to 2, the second () extends the run to 4, and the final unmatched ) empties the stack and becomes a fresh boundary. The answer stays at best = 4.

Pseudocode

best = 0
stack = [-1]                       # sentinel boundary just left of the string
for each index i with char ch in s:
    if ch == "(":
        push i onto stack
    else:                          # ch == ")"
        pop the top
        if stack is now empty:
            push i                  # unmatched ")" — new boundary
        else:
            best = max(best, i - top of stack)
return best

The Python solution

def longest_valid(s):
    best = 0
    stack = [-1]
    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                best = max(best, i - stack[-1])
    return best

• stack holds indices, and starts with -1 so the first valid run measures correctly.
• On ( we just record where the open paren sits with stack.append(i).
• On ) we always pop() first — that consumes either a matching ( or the sentinel/last-unmatched boundary.
• If the pop left the stack empty, this ) had no partner; we push i as the new boundary.
• Otherwise a valid run is open: i - stack[-1] is its length, and max keeps the best seen.

Complexity

We make a single pass, and every index enters and leaves the stack at most once, so the work is O(n). The stack can hold up to n indices, giving O(n) space.

When this pattern shows up

Practice