Example 1
ready- Input
s = "(()"- Expected
2- Why
- the first opening and the closing parenthesis form a length-2 run
Longest Valid Parentheses
50 min · longestValidParentheses()One stray parenthesis can split a long string into several smaller islands of valid structure.
You're given a string s containing only ( and ). Return the length of its longest
contiguous substring — one unbroken run of characters — that is well-formed:
every opening parenthesis has a later closing partner, and pairs close in the reverse
order they opened.
A few ground rules:
- You may start and stop anywhere in
s, but you can't skip characters inside the run. - Unmatched parentheses outside the chosen run don't matter.
- Length counts characters, so every nonzero answer is even.
- The empty string has answer
0.
Constraints
0 <= s.length <= 100_000sconsists only of(and).
Hints
Measure one starting point
Pick a start and scan right with a balance: ( adds one and ) subtracts one. A
zero balance marks a valid candidate; a negative balance means this start can never
recover.
Keep the unmatched positions
Store indices of unmatched opening parentheses. When a closing parenthesis arrives, match it by popping. The index now on top tells you where the current valid run began.
Give the stack a base
Begin with -1 as the boundary before the string. If a closing parenthesis has
nothing to match, its own index becomes the new boundary. Otherwise the current
valid length is i - stack[-1].
Follow-up
Can you reach O(1) extra space by counting opens and closes left-to-right, then repeating the scan right-to-left to catch the imbalance the first direction misses?
Visible cases
Examples
Example 2
ready- Input
s = ")()())"- Expected
4- Why
- the middle run ()() is well-formed and has length 4
Example 3
ready- Input
s = ""- Expected
0- Why
- an empty string contains no nonempty valid run
Interview signal
Asked at
AmazonGoogleMeta
Scan every start
Treat each index as a possible beginning. Move right while maintaining a balance: add
one for ( and subtract one for ). Balance zero means the current substring is valid;
a negative balance means this starting point is broken for good.
def longest_valid_parentheses(s: str) -> int:
best = 0
for start in range(len(s)):
balance = 0
for end in range(start, len(s)):
balance += 1 if s[end] == "(" else -1
if balance < 0:
break
if balance == 0:
best = max(best, end - start + 1)
return bestEvery well-formed substring appears during the scan from its own first index. Time O(n²) in the worst case, such as a long run of opening parentheses. Space O(1).
Base-index stack
Instead of restarting, keep the indices that still block the left edge of a valid run.
The stack begins with -1, the boundary just before the string.
- An opening parenthesis might need a future match, so push its index.
- For a closing parenthesis, pop one possible match.
- If that empties the stack, this closing parenthesis is unmatched. Push its index as the new boundary.
- Otherwise, the run ending at
ibegins just after the index now on top.
def longest_valid_parentheses(s: str) -> int:
stack = [-1]
best = 0
for i, char in enumerate(s):
if char == "(":
stack.append(i)
continue
stack.pop()
if not stack:
stack.append(i)
else:
best = max(best, i - stack[-1])
return bestThe top is always the last unmatched boundary before the current valid suffix. That
makes i - stack[-1] exactly its length, even when several valid groups touch.
Time O(n) — each index is pushed and popped at most once. Space O(n) for unmatched indices in the worst case.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
2
Run: visible + custom · Submit: full suite