Longest Valid Parentheses
You get a string s made only of the characters ( and ). Find the longest substring (a run of consecutive characters) that is well formed: every ( in it is closed by a later ) in it, and the pairs nest properly, as in (()()). Return the length of that substring, or 0 when not even () appears.
Function
- sstring
- a string of ( and ) characters
- Returnsinteger
- the length of the longest well-formed substring, or 0 if there is none
Constraints
1 ≤ s.length ≤ 6 × 104- Every character of
sis(or).
Examples
- Input
- s = "()(())"
- Output
- 6
- Explanation
- The whole string is well formed:
()followed by(()). Two well-formed pieces side by side make one, so the answer is all 6 characters.
- Input
- s = "())((())"
- Output
- 4
- Explanation
- The
)at index 2 has no partner, so no answer crosses it, and the(at index 3 never closes. The longest piece is(())at indices 4 to 7, length 4, which beats the()at the start.
- Input
- s = "))(("
- Output
- 0
- Explanation
- Both
)come before both(, so no(is ever closed and the answer is 0.
Follow-up
Can you also report where the longest well-formed substring starts, choosing the leftmost one when several have the same length?
Hints
Open them one at a time. Each one gives away a little more.
Read a substring from left to right and keep a balance: +1 for
(, -1 for). What does the balance do on a well-formed substring, and what does a)that drives it below zero tell you about every substring that crosses it?Keep a stack of the indices of the
(characters that are still open. When a)closes the one on top, the well-formed run that ends here starts right after whatever index is now left on top. What should sit on the stack when nothing is open?Start the stack with -1, the index right before the string. Push the index of every
(. On a), pop; if the stack is now empty, this)can never be matched, so push its index as the new base; otherwise the current run isiminus the index on top. Keep the largest run you measure.
Solution
Well-formed pieces join when they touch, so () and (()) side by side make one run. A stray character, like the ) in ())(()), cuts the string so no run crosses it. A stack of indices with a base marker tracks where the current run began in one pass; two counter passes do it in O(1) memory.
Grow a substring from every start
Correct, but does not finish on the largest tests
Intuition
Fix a start and walk right with a balance: +1 for (, -1 for ). The stretch is well formed exactly when the balance comes back to 0 without dropping below it, so record its length each time it hits 0. Below 0, stop: that ) stays unmatched in every longer stretch from this start.
In 59998 ( followed by (), every start walks to the end: about n²/2 = 1.8 × 10^9 steps for n = 6 × 10^4.
Algorithm
- Set
bestto 0. - For each start, set
balanceto 0 and walk the end from the start to the last character. - Add 1 for
(and subtract 1 for). - If
balanceis below 0, stop this start. If it is 0, updatebestwithend - start + 1. - Return
best.
def longestValidParentheses(s):
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:
# A ')' without a partner: no longer run starts here
break
if balance == 0:
best = max(best, end - start + 1)
return bestStack of indices with a base marker
Intuition
Push indices, and keep one extra index at the bottom: the base, the position right before the current run, -1 at the start. On (, push its index. On ), pop. If the stack is now empty, you popped the base: this ) can close nothing, so its index becomes the new base. Otherwise the top is the last character before the run ending at i, an open ( or the base, so the run is i - top.
The base is what joins touching pieces. On ()(()), the last ) pops index 2 and finds -1 on top: 5 - (-1) = 6. On ())((()), index 2 pops the base and becomes it, and the last ) pops 4 and finds the open ( at 3: 7 - 3 = 4.
Each index is pushed and popped at most once: O(n) time.
Algorithm
- Start a stack holding -1 and set
bestto 0. - For each index
i, pushiifs[i]is(. - If it is
), pop once. - If the stack is now empty, push
ias the new base. Otherwise updatebestwithi - top. - Return
best.
def longestValidParentheses(s):
# The bottom of the stack is the index just before the current run
stack = [-1]
best = 0
for i, ch in enumerate(s):
if ch == "(":
stack.append(i)
else:
stack.pop()
if not stack:
# This ')' has no partner: it becomes the new base
stack.append(i)
else:
best = max(best, i - stack[-1])
return bestCount opens and closes in two passes
Intuition
Walk left to right counting opens and closes since the last reset. Equal counts mean everything since the reset is well formed, length 2 × closes. When closes pulls ahead, a ) has no partner, so reset both. A ( that never closes keeps opens ahead for good, so on (() this pass finds nothing. Walk again right to left, resetting when opens pulls ahead, and keep the larger answer.
Two passes are enough. The longest run is fenced by unmatchable characters or the ends. If its left fence is a stray ) or the start, the left pass resets where the run begins. If its left fence is a stray (, its right fence cannot be a ), which would close that ( and lengthen the run, so the right pass catches it.
Algorithm
- Set
best,opensandclosesto 0. - Walk left to right, counting each character. When the counts are equal, update
bestwith2 × closes. Whenclosesis larger, reset both to 0. - Reset both counters, then walk right to left the same way, resetting when
opensis larger. - Return
best.
def longestValidParentheses(s):
best = 0
# Left to right: more ')' than '(' ends every run that started earlier
opens = closes = 0
for ch in s:
if ch == "(":
opens += 1
else:
closes += 1
if opens == closes:
best = max(best, 2 * closes)
elif closes > opens:
opens = closes = 0
# Right to left: catches the runs that an unmatched '(' hid from the first pass
opens = closes = 0
for ch in reversed(s):
if ch == "(":
opens += 1
else:
closes += 1
if opens == closes:
best = max(best, 2 * opens)
elif opens > closes:
opens = closes = 0
return best
Pitfalls and edge cases
- Counting matched pairs over the whole string.
())((())has 3 pairs, but they do not all touch, so the answer is 4, not 6. - Measuring a run from the matching
(. On()(())the last)matches index 2, which gives 4 and misses the()in front. - Starting with an empty stack instead of the base -1 (0 in Lua and R, whose positions start at 1). The first
)of())then has nothing to measure against. - Running the counters in one direction only.
(()returns 0 left to right, and())returns 0 right to left; the answer is 2 for both. - Resetting the counters when they are equal. The run may still grow, as in
()().
Frequently asked questions3
What is the time complexity of Longest Valid Parentheses?
The stack solution and the two-pass counter solution both run in O(n) time. The stack needs O(n) memory in the worst case, such as a string of only (, while the counters need O(1). Trying every start is O(n²).
Is there a dynamic programming solution for Longest Valid Parentheses?
Yes. Let end[i] be the longest well-formed run ending at i, 0 when s[i] is (. If s[i-1] is (, end[i] = end[i-2] + 2. Otherwise let j = i - end[i-1] - 1; if s[j] is (, end[i] = end[i-1] + 2 + end[j-1]. The largest end[i] is the answer.
How is this different from Valid Parentheses?
Valid Parentheses asks whether the whole string is well formed, a yes or no that one counter or stack answers. Here you want the longest well-formed substring, so you also track where each run starts and restart after a character that can never be matched.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def longestValidParentheses(s):
# Write code hereTest #1
Test #2
Test #3
Argument
s = "()(())"
Expected Output
6