Longest Valid Parentheses
MediumStack the indices, measure from the last unmatched
Problem
Given a string of '(' and ')', return the length of the longest valid (well-formed) parentheses substring.
Track indices of unmatched brackets on a stack; the distance past the last unmatched one is a valid run.
The idea
Push indices of unmatched positions and, on a match, measure back to whatever index is now on top — that is the start of the current valid run. Seeding the stack with -1 gives a base for runs that start at index 0.
The trick
- Seed with -1 so the first valid run measures correctly.
- Push the index of an unmatched ')' as the new base.
- A two-pass counter scan solves it in O(1) space.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — ')()())' Values: 0.
1stack=[-1]2for i,c: if '(' push i; else pop; if empty push i else ans=max(ans,i-top)Input
- array
- [0]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- s = "(()"
- Output:
- 2
- Explanation:
- The "()" at the end has length 2.
Example 2
- Input:
- s = ")()())"
- Output:
- 4
- Explanation:
- "()()" in the middle → length 4.
Example 3
- Input:
- s = ""
- Output:
- 0
- Explanation:
- Empty string → 0.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.