How do you approach Longest Valid Parentheses?

Try using a stack to track unmatched parentheses indices.

What is the time complexity of Longest Valid Parentheses?

Time complexity: O(n). Space complexity: O(n).

What are common mistakes on Longest Valid Parentheses?

Popping without first checking the stack is non-empty. Ignoring what is left on the stack at the end - a non-empty stack is usually itself part of the answer. Pushing values where the problem needs indices back.

gitGood.dev

← Back to problems

Longest Valid Parentheses

HardAlgorithms

Description

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

Example 1

Input: s = "(()"

Output: 2

Explanation: The longest valid parentheses substring is "()".

Example 2

Input: s = ")()())"

Output: 4

Explanation: The longest valid parentheses substring is "()()".

Example 3

Input: s = ""

Output: 0

Constraints

- 0 <= s.length <= 3 * 10^4 - s[i] is '(' or ')'

Longest Valid Parentheses: approach, complexity and pitfalls

A hard stack problem, graded against 7 test cases (4 of them hidden).

The pattern: Stack

Last-in-first-out processing - matching, nesting, and deferred evaluation.

Reach for it when you see: Balanced brackets, nested structures, undo/back semantics, or expression evaluation.

If you are stuck

Show the 3-step hint ladder

Try using a stack to track unmatched parentheses indices.
Initialize the stack with -1 as a base index.
When you see ')', pop from the stack. If the stack is empty, push the current index as the new base.

The optimal approach

Show the approach: Stack-based Approach

Use a stack initialized with -1 as the base. For each '(', push its index. For each ')', pop the top. If the stack becomes empty, push the current index as the new base. Otherwise, the current valid length is i - stack.top().

Time: O(n)
Space: O(n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty string. An empty string is passed, so index reads and any assumption of at least one character are tested.

Common Stack mistakes

These apply to the pattern as a whole, not just this problem.

Popping without first checking the stack is non-empty.
Ignoring what is left on the stack at the end - a non-empty stack is usually itself part of the answer.
Pushing values where the problem needs indices back.