Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Longest Valid Parentheses

LeetCode #32Hard
Stack of indices · a base below every run

Given a string containing only the characters ( and ), return the length of the longest contiguous substring that forms a well-formed (properly matched) sequence of parentheses.

Asked atAmazonGoogleAdobe
step 1 / 31
)
(
)
(
)
)
[0][1][2][3][4][5]
Brute force · balance from every start
▸
1given s
2best ← 0
3for i ← 0 to n − 1:
4    bal ← 0
5    for j ← i to n − 1:
6        bal += (s[j] == "(" ? +1 : −1)
7        if bal < 0: break
8        if bal == 0: best = max(best, j − i + 1)
9return best
state
  • s")()())"

line 1Find the LONGEST contiguous substring that is a valid bracket sequence. A substring is valid iff its running balance never dips below 0 and ends at exactly 0.