32. Longest Valid Parentheses

Edited by Charles

Hard · Python · Dynamic Programming

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

Given a string s containing only:

return the length of the longest valid parentheses substring.

Original study notes follow, including intermediate snippets and earlier attempts.

Problem

Given a string s containing only:

'(' and ')'

return the length of the longest valid parentheses substring.

Example

Input:
s = ")()())"

Output:
4

Because the longest valid parentheses substring is:

"()()"

with length:

4

The most important part of this problem is the definition of dp[i].

Define:

dp[i] = the length of the longest valid parentheses substring
        that MUST end at index i

The key phrase is:

MUST end at i

It does not mean:

the longest valid parentheses substring in s[0:i+1]

Consider:

s = ")()())"

index:  0  1  2  3  4  5
char:   )  (  )  (  )  )
dp:     0  0  2  0  4  0

At index 4:

) ( ) ( ) )
  └─────┘
    ()()

There is a valid substring of length 4 ending at index 4.

Therefore:

dp[4] = 4

But at index 5:

)()())
     ↑
     i

there is no valid parentheses substring ending at index 5.

Therefore:

dp[5] = 0

So:

dp[-1] == 0

even though the answer is 4.

Therefore, the final answer is:

max(dp)

rather than:

dp[-1]

A valid parentheses substring must end with:

)

It cannot end with:

(

Therefore, if:

s[i] == '('

then:

dp[i] = 0

We only need to process positions where:

s[i] == ')'

Suppose:

...()
   ↑↑
 i-1 i

That is:

s[i - 1] == '('
s[i] == ')'

Then:

s[i-1:i+1] = "()"

which gives us a new valid pair of length 2.

But there may already be a valid parentheses substring immediately before this pair.

For example:

()()

At the last ):

index:  0 1 2 3
char:   ( ) ( )
              ↑
              i

The current:

()

contributes:

2

and the previous valid substring contributes:

dp[i - 2]

Therefore:

dp[i] = dp[i - 2] + 2

If i < 2, there is nothing before the current ().

So we write:

dp[i] = (dp[i - 2] if i >= 2 else 0) + 2

Now consider:

...))
   ↑↑
 i-1 i

We cannot directly match:

))

However, dp[i-1] may tell us that there is already a valid parentheses substring ending at i-1.

For example:

(())

At the final ):

index:  0 1 2 3
char:   ( ( ) )
              ↑
              i

We already know:

dp[i - 1] = dp[2] = 2

because:

()

ends at index 2.

Graphically:

( ( ) )
↑ └─┘ ↑
j     i

We want to find the character immediately before the valid substring ending at i-1.

The valid substring ending at i-1 has length:

dp[i - 1]

So we jump backward by that many characters and then one additional position:

j = i - dp[i - 1] - 1

This j represents:

The position that might contain the ( matching the current s[i] == ')'.

For:

(())

we have:

i = 3
dp[i - 1] = 2

j = 3 - 2 - 1
  = 0

So:

index:  0 1 2 3
char:   ( ( ) )
        ↑ └─┘ ↑
        j     i

Now:

s[j] == '('

so s[j] can match the current s[i].

If:

j >= 0 and s[j] == '('

then we can combine:

( + valid substring + )

The existing valid substring has length:

dp[i - 1]

The new outer pair contributes:

2

Therefore:

dp[i] = dp[i - 1] + 2

But there is one more important case.

Consider:

()(())

The final (()) is valid, but there is also another valid substring before it:

() + (())

We want to combine them into:

()(())

So after finding j, we also need to check whether there is another valid substring ending at:

j - 1

Therefore:

dp[i] = dp[i - 1] + 2 + dp[j - 1]

If j == 0, then there is nothing before j.

So:

dp[i] = dp[i - 1] + 2

if j >= 1:
    dp[i] += dp[j - 1]

Consider:

() (())
^^ ^^^^

The current structure is:

[previous valid] ( [current valid] )

The part:

( [current valid] )

gives:

dp[i - 1] + 2

But there may also be another valid substring immediately before the matching (.

That substring ends at:

j - 1

Its length is:

dp[j - 1]

Therefore:

dp[i]
=
previous valid substring
+
current inner valid substring
+
new pair

=
dp[j - 1]
+
dp[i - 1]
+
2

The entire problem can be summarized into two cases.

Case 1

...()
   ↑↑
 i-1 i

If:

s[i - 1] == '('

then:

dp[i] = dp[i - 2] + 2

Case 2

...(valid))
           ↑
           i

If:

s[i - 1] == ')'

first find:

j = i - dp[i - 1] - 1

If:

j >= 0 and s[j] == '('

then:

dp[i] = dp[i - 1] + 2 + dp[j - 1]

where dp[j - 1] is included only when:

j >= 1

s[i] == ')'
│
├── Case 1: s[i-1] == '('
│
│       ... ( )
│           ↑ ↑
│          i-1 i
│
│       dp[i]
│       = dp[i-2] + 2
│
│
└── Case 2: s[i-1] == ')'

        ... ( [valid] )
            ↑         ↑
            j         i

        j = i - dp[i-1] - 1

        if s[j] == '(':

        dp[i]
        = dp[i-1] + 2 + dp[j-1]

Consider:

s = ")()())"

index:  0  1  2  3  4  5
char:   )  (  )  (  )  )

Initially:

dp = [0, 0, 0, 0, 0, 0]

i = 1

s[1] = '('

A valid parentheses substring cannot end with (.

Therefore:

dp[1] = 0

i = 2

s[2] = ')'
s[1] = '('

This is Case 1:

()

Therefore:

dp[2] = dp[0] + 2
      = 2

Now:

dp = [0, 0, 2, 0, 0, 0]

i = 3

s[3] = '('

Therefore:

dp[3] = 0

i = 4

s[4] = ')'
s[3] = '('

Again, Case 1:

dp[4] = dp[2] + 2
      = 2 + 2
      = 4

Now:

dp = [0, 0, 2, 0, 4, 0]

The valid substring ending at index 4 is:

) ( ) ( ) )
  └─────┘
    ()()

i = 5

s[5] = ')'
s[4] = ')'

This is Case 2.

Calculate:

j = i - dp[i - 1] - 1

So:

j = 5 - dp[4] - 1
  = 5 - 4 - 1
  = 0

But:

s[0] = ')'

not:

'('

Therefore, the current ) cannot form a valid substring ending at index 5.

So:

dp[5] = 0

Final DP array:

index:  0  1  2  3  4  5
char:   )  (  )  (  )  )
dp:     0  0  2  0  4  0

Therefore:

max(dp) = 4

This is an important detail.

Our definition is:

dp[i]
=
longest valid parentheses substring
that MUST end at index i

Therefore:

dp[-1]

only tells us the longest valid substring that ends at the last character.

It does not represent the maximum over the entire string.

For:

")()())"

we have:

dp = [0, 0, 2, 0, 4, 0]

So:

dp[-1] == 0

but:

max(dp) == 4

Therefore, the answer is:

max(dp)

or we can maintain a global maximum:

res = max(res, dp[i])

Time Complexity

We traverse the string once:

O(n)

Space Complexity

We use a DP array of length n:

O(n)

The most important definition is:

dp[i]
=
the length of the longest valid parentheses substring
ending exactly at index i

Therefore:

s[i] == '('
→ dp[i] = 0

When:

s[i] == ')'

there are two cases:

Case 1:

...()

dp[i] = dp[i-2] + 2

and:

Case 2:

... ( [valid] )
    ↑         ↑
    j         i

j = i - dp[i-1] - 1

If:

s[j] == '('

then:

dp[i]
=
dp[i-1] + 2 + dp[j-1]

Finally, remember:

dp[i] = best valid substring ENDING at i

so the final answer is:

max(dp)

not:

dp[-1]

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	September 17, 2026

Python solution

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)

        if n == 0:
            return 0

        dp = [0] * n
        res = 0

        for i in range(1, n):
            if s[i] == ')':

                # Case 1: ...()
                if s[i - 1] == '(':
                    dp[i] = (dp[i - 2] if i >= 2 else 0) + 2

                # Case 2: ...))
                else:
                    j = i - dp[i - 1] - 1

                    if j >= 0 and s[j] == '(':
                            # Case (())
                        dp[i] = dp[i - 1] + 2

                        if j >= 1:
                        # Case ()(())
                            dp[i] += dp[j - 1]

                res = max(res, dp[i])

        return res

---

Back to Bonus Dynamic Programming · All Algorithm notes