Free Stacks and queues lessonsStacks and queues · Stage 1 · Matching brackets · Step 2

The longest run that matches

Find the longest stretch of a bracket string that is balanced, by keeping the positions of the unmatched brackets on a stack. About 16 minutes.

Positions, not characters

A valid run is a stretch like ()(()) with every bracket matched. To measure one you need its start, so push positions rather than characters. Put a marker, minus 1, at the bottom: the position before the string.

An opener pushes its position. A closer pops. If the stack is still not empty, the top is the position just before the current run, so the run ends here and has length i minus top.

Opener: push its position.

Closer that matches: run length is i minus the new top.

In code

stack = [-1]
for i, ch in enumerate(s):
    if ch == "(":
        stack.append(i)
    else:
        stack.pop()

Longest valid run in ) ( ) ( ) ) at positions 0 to 5.

)

(

)

(

)

A closer pops the marker and empties the stack. Position 0 is the new marker.

Move 1 of 6

A closer that cannot match

If popping empties the stack, the closer had no opener to match: even the bottom marker was taken. This closer position cannot be part of any valid run, so it becomes the new bottom marker.

After that, new runs can only start to its right. Keep the best length seen so far, and return it at the end. An empty string gives 0.

Stack empty after pop: push this position as the new marker.

Best: the largest run length seen.

In code

if not stack:
    stack.append(i)
else:
    best = max(best, i - stack[-1])

Quick check

A closer arrives, and popping leaves the stack empty. What do you do?

APush this closer's position as the new bottom marker
BRecord a new best length
CIgnore it and carry on

Show the answer

Push this closer's position as the new bottom marker. This closer cannot be matched, so no valid run can cross it.

Your problem

Longest valid parentheses

Given a string s made only of ( and ), return the length of the longest substring (a run of consecutive characters) that is a valid, balanced bracket string.

Example

s = ")()())" → 4

0 ≤ length of s ≤ 100,000 · s has only ( and )

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.