Longest Valid Parentheses

Q: Is there a dynamic programming solution for Longest Valid Parentheses?

Yes. Let end[i] be the length of the longest well-formed substring that ends at index i ; it is 0 when s[i] is ( . If s[i-1] is ( , then end[i] = end[i-2] + 2 . If it is ) , look at j = i - end[i-1] - 1 , the character before the run that ends at i-1 : when s[j] is ( , it wraps that run, and end[i] = end[i-1] + 2 + end[j-1] , where the last term joins a run that touches it on the left. The answer is the largest end[i] , in O(n) time and memory.

Q: Why is one pass with counters not enough?

A left-to-right pass resets only when ) outnumbers ( . An extra ( that never closes keeps the counts apart for the rest of the string, so the pass never sees them meet. In (() it ends with 2 opens and 1 close and finds nothing. Reading right to left treats the stray ( the way the first pass treats a stray ) , so the two passes together cover every run.

HardStack Dynamic programming

+10

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

longestValidParentheses(s: string) → integer

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 × 10⁴
Every character of s is ( or ).

Examples

Input: s = "()(())"
Output: 6
Explanation: The whole string is well formed: () followed by (()). Two well-formed pieces side by side make one well-formed piece, so the answer is all 6 characters.

Input: s = "())((())"
Output: 4
Explanation: The ) at index 2 has no partner, so no answer can cross it, and the ( at index 3 is never closed. The longest piece is (()) from index 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. No substring is well formed and the answer is 0.

+21 hidden tests on Submit

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.

0 of 3 opened

Solution

Two things make this harder than checking one string. Well-formed pieces join when they touch, so () and (()) next to each other count as one run of 6. And one stray character, such as the ) in ())(()), cuts the string so no answer crosses it. Testing every start costs O(n²). The fix is to remember where the current run began: a stack of indices with a base marker at the bottom does it in one pass, and two passes of plain counters do it with no stack at all.

Grow a substring from every start

Correct, but does not finish on the largest tests

Intuition

Read a substring from left to right with a balance that adds 1 for ( and subtracts 1 for ). The substring is well formed exactly when the balance never drops below 0 and ends at 0. Below 0 means a ) arrived with nothing open to close.

So fix a start and walk right, updating the balance one character at a time. Every time it comes back to 0, the stretch from the start to here is well formed, and you record its length. The moment it goes below 0, stop: that ) stays unmatched in every longer stretch from this start. Every well-formed substring has some start, and you try every end for it, so nothing is missed.

The cost is the problem. In a string of 59998 ( followed by (), the balance never drops below 0, so every start walks to the end: about n²/2 = 1.8 × 10^9 steps for n = 6 × 10^4. The large tests are built like that. (Checking each substring from scratch instead of growing it would be worse still, O(n³).)

Algorithm

Set best to 0.
For each start, set balance to 0 and walk the end from the start to the last character.
Add 1 for ( and subtract 1 for ).
If balance is below 0, stop this start. If it is 0, update best with the stretch length end - 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 best

Stack of indices with a base marker

Intuition

Matching brackets with a stack is familiar: push each (, pop one for each ). Here you also need lengths, so push indices, and keep one extra index at the bottom of the stack: the base, the position right before the run you are in. At the start nothing has been read, so the base is -1.

On (, push its index. On ), pop. Two things can happen. If the stack is now empty, you popped the base, so this ) had nothing to close. No well-formed substring can contain it, and it becomes the new base: push its index. Otherwise the index left on top is the last character before the run that ends at i: either a ( that is still open or the base. Everything after it up to i is matched, and the run cannot reach further left, so its length is i - top.

Here is ())((()):

i = 0, (: push 0. Stack [-1, 0].
i = 1, ): pop 0. The top is -1, so the run is 1 - (-1) = 2.
i = 2, ): pop -1 and the stack is empty. This ) has no partner, so push 2 as the new base. Stack [2].
i = 3, 4, 5, three (: push them. Stack [2, 3, 4, 5].
i = 6, ): pop 5. The top is 4, so the run is 6 - 4 = 2.
i = 7, ): pop 4. The top is 3, so the run is 7 - 3 = 4, the answer.

The base is what makes touching pieces join. On ()(()), the first pair measures 1 - (-1) = 2, and the last ) pops index 2 and finds -1 on top again, so it measures 5 - (-1) = 6. Measuring from the matching ( instead would give 4 and miss the () in front. Each index is pushed and popped at most once, so the pass is O(n), and the stack can hold up to n+1 indices.

Algorithm

Start a stack holding -1 and set best to 0.
For each index i, push i if s[i] is (.
If it is ), pop once.
If the stack is now empty, push i as the new base. Otherwise update best with i - 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 best

Count opens and closes in two passes

Intuition

The stack only ever tells you where the current run began. Two counters can do that too. Walk left to right counting opens and closes since the last reset. When they are equal, everything since the reset is well formed, with length 2 × closes. When closes pulls ahead, a ) has no partner, the same moment the stack lost its base, so reset both counters to 0.

One pass is not enough. A ( that never closes keeps opens ahead for good, and the counts never meet again. On (() the left pass ends with 2 opens and 1 close and reports nothing, though () is right there. So walk a second time, from right to left, with the roles swapped: reset when opens pulls ahead. Read backwards, (() gives a close, then an open (equal: length 2), then an open that resets. The answer is the larger of the two passes.

Why two passes catch every run: the longest run is fenced in by characters that can never be matched, or by the ends of the string. If its left fence is a stray ) or the start, the left pass resets right where the run begins and sees the counts meet where it ends. If its left fence is a stray (, its right fence cannot be a ), because that ) would close the stray ( and the run would be longer. So the right fence is a stray ( or the end, and the right pass catches the run the same way. Each pass reads the string once with two integers, so the time is O(n) and the extra memory O(1).

Algorithm

Set best to 0, and opens and closes to 0.
Walk left to right, counting each character. When the counts are equal, update best with 2 × closes. When closes is larger, reset both to 0.
Reset both counters, then walk right to left the same way, except that you reset when opens is 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

Most wrong answers count the right pairs in the wrong places, or lose the start of a run.

Counting matched pairs over the whole string. ())((()) has 3 pairs, but they are not all touching, and 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. Measure from the index left on the stack after the pop.
Starting with an empty stack. The first ) of ()) then has nothing to measure against, and an unmatched ) pops from an empty stack. The -1 base fixes both.
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. Equal counts mean the run may still grow, as in ()(); reset only when one side pulls ahead.
In Lua and R positions start at 1, so the first base is 0, not -1.

Frequently asked questions4

What is the time complexity of Longest Valid Parentheses?

Both the stack solution and the two-pass counter solution read each character a constant number of times, so they 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²).

Why does the stack start with -1?

The run length is the current index minus the index right before the run. For a run that starts at index 0, that earlier index is -1, one step before the string. Pushing -1 first means the stack is never empty when a matched ) measures, and when an unmatched ) pops it, that ) takes over as the new base.

Is there a dynamic programming solution for Longest Valid Parentheses?

Yes. Let end[i] be the length of the longest well-formed substring that ends at index i; it is 0 when s[i] is (. If s[i-1] is (, then end[i] = end[i-2] + 2. If it is ), look at j = i - end[i-1] - 1, the character before the run that ends at i-1: when s[j] is (, it wraps that run, and end[i] = end[i-1] + 2 + end[j-1], where the last term joins a run that touches it on the left. The answer is the largest end[i], in O(n) time and memory.

Why is one pass with counters not enough?

A left-to-right pass resets only when ) outnumbers (. An extra ( that never closes keeps the counts apart for the rest of the string, so the pass never sees them meet. In (() it ends with 2 opens and 1 close and finds nothing. Reading right to left treats the stray ( the way the first pass treats a stray ), so the two passes together cover every run.

Python

def longestValidParentheses(s):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

s = "()(())"

Expected

Longest Valid Parentheses

Function

Constraints

Examples

Hints

Solution

Grow a substring from every start

Stack of indices with a base marker

Count opens and closes in two passes

Pitfalls and edge cases

Frequently asked questions4

Similar problems