Longest Valid Parentheses

Counting matching pairs is not enough. The pairs must form one contiguous, well-formed region, and valid regions can nest, touch, or be separated by an unmatched parenthesis.

The useful direction is to define a one-dimensional state for the best valid substring ending at each index. Then derive how a closing parenthesis reaches backward to connect with an opening boundary.

Start with the exact contract

Given a string containing only ( and ), return the length of its longest contiguous well-formed parentheses substring.

The result is not a subsequence length. You cannot skip characters. An unmatched parenthesis breaks contiguity and separates usable regions.

Examples:

"(()"    -> 2
")()())" -> 4
""       -> 0

The input can be empty and can contain up to 3 * 10^4 characters, so repeatedly validating every substring is the wrong architecture. That approach rescans overlapping ranges and quickly becomes quadratic or worse.

The dynamic-programming plan is:

1. Compute the best valid substring ending at each position.
2. Reuse earlier results when a new closing parenthesis extends them.
3. Track the maximum over all ending positions.

The answer is not necessarily the state at the final index. The longest valid region may be entirely inside the string.

Recognize the one-dimensional state

Only ) can end a nonempty valid parentheses substring. An opening parenthesis can begin a structure, but it cannot close one.

Define:

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

If s[i] is (, then:

dp[i] = 0

The same is true when s[i] is ) but no valid substring can end there.

This state is deliberately local: it describes the right boundary of a candidate span. The left boundary is recovered when a closing parenthesis looks backward.

That boundary is the important idea. Unmatched parentheses act as barriers. A valid suffix can grow only if the characters immediately before it provide a legal matching opening parenthesis or a preceding valid block.

Invariant: After processing index i, dp[i] is the maximum length of a well-formed contiguous substring whose final character is s[i].

Maintain a separate best value because valid substrings can end anywhere:

best = max(dp[0], dp[1], ..., dp[n - 1])

Derive the two closing cases

Consider an index i where s[i] == ')'. There are two ways a valid substring can end there.

Case 1: The current close forms ()

If the previous character is (, then s[i - 1:i + 1] is a valid pair.

The pair may also have a valid block directly before it:

... valid block ... ( )
                     i-1 i

Therefore:

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

when i >= 2. If there is no position i - 2, the preceding contribution is zero.

For example, in "()()", the second pair does not stand alone:

dp[1] = 2
dp[3] = dp[1] + 2 = 4

The recurrence joins adjacent valid blocks.

Case 2: The current close follows a valid suffix

Now suppose s[i - 1] == ')'.

The substring represented by dp[i - 1] is a valid suffix immediately before s[i]. Let:

inner = dp[i - 1]

That suffix occupies:

[i - inner, i - 1]

The possible matching opening parenthesis must be immediately before it:

candidate = i - inner - 1

If s[candidate] == '(', then that opening parenthesis can wrap the valid suffix:

( valid suffix )

The resulting length is:

inner + 2

There may also be another valid block immediately before candidate. That block ends at candidate - 1, so add:

dp[candidate - 1]

The complete recurrence is:

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

with the preceding contribution treated as zero when candidate == 0.

The crucial calculation is:

candidate = i - dp[i - 1] - 1

Do not inspect merely s[i - 2]. The valid suffix before the current close may be several characters long. You must jump over the entire suffix to find the boundary that could contain its matching opening parenthesis.

For example, in "(())":

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

At index 3:

inner = dp[2] = 2
candidate = 3 - 2 - 1 = 0

s[0] is (, so the outer pair wraps the valid inner pair:

dp[3] = 2 + 2 + 0 = 4

Recurrence summary

For each index i:

if s[i] == '(':
    dp[i] = 0

elif i >= 1 and s[i - 1] == '(':
    dp[i] = 2 + (dp[i - 2] if i >= 2 else 0)

else:
    inner = dp[i - 1]
    candidate = i - inner - 1

    if candidate >= 0 and s[candidate] == '(':
        dp[i] = inner + 2
        if candidate >= 1:
            dp[i] += dp[candidate - 1]

Any case that fails its boundary check leaves dp[i] at zero.

Prove the DP invariant

We prove that dp[i] is exactly the longest valid substring ending at i.

If s[i] == '(', no nonempty valid parentheses sequence can end with an opening parenthesis. Setting dp[i] = 0 is correct.

Now suppose s[i] == ')'. A valid substring ending at i must close in one of two structural ways:

1. The final two characters are ().
2. The final character closes an opening parenthesis that appears immediately before a valid suffix ending at i - 1.

In the first case, the pair contributes two characters. Any valid block directly before it is exactly the state at i - 2, so adding dp[i - 2] captures the longest contiguous extension.

In the second case, dp[i - 1] identifies the valid suffix directly before the current close. The index:

i - dp[i - 1] - 1

is the only possible position for the opening parenthesis that wraps that suffix. If it is not (, the current close cannot extend that suffix. If it is (, the wrapped region contributes dp[i - 1] + 2, and dp[candidate - 1] captures a valid block directly before the opening boundary.

Thus every valid substring ending at i is represented by one of the recurrence cases, and every accepted recurrence case forms a valid contiguous substring. Taking the maximum over all dp[i] finds the global answer because every candidate substring has some final index.

The recurrence passes examples. The invariant explains why it works.

Trace nesting, joins, and barriers

The string ")()())" contains a barrier at index 0 and a valid region in the middle.

i	s[i]	Relevant state	Candidate	dp[i]	best
0	)	no preceding opening boundary	—	0	0
1	(	opening cannot end a valid span	—	0	0
2	)	adjacent (); previous state is dp[0]	—	2	2
3	(	opening cannot end a valid span	—	0	2
4	)	adjacent (); add dp[2]	—	4	4
5	)	inner = dp[4] = 4	0	0	4

At index 4, the adjacent-pair case joins two blocks:

() + () = ()()

At index 5, the current close cannot find a matching opening parenthesis at index 0; that position contains ). The unmatched close at the beginning remains a barrier.

For a nested example, "(())" produces:

i	s[i]	inner	candidate	dp[i]
0	(	—	—	0
1	(	—	—	0
2	)	—	—	2
3	)	2	0	4

Several tempting approaches fail here:

• Counting pairs ignores whether they form one contiguous span.
• Looking only for adjacent () misses nesting.
• Treating valid blocks as permanently independent misses joins such as "()()".
• Looking only at the previous character misses the boundary beyond a complete valid suffix.

The state must remember both the suffix length and the boundary just before it.

Implement the Python solution safely

Here is a direct Python implementation of the recurrence:

def longest_valid_parentheses(s: str) -> int:
    n = len(s)
    dp = [0] * n
    best = 0

    for i in range(n):
        if s[i] == ')':
            # Case 1: form an adjacent "()".
            if i >= 1 and s[i - 1] == '(':
                dp[i] = 2
                if i >= 2:
                    dp[i] += dp[i - 2]

            # Case 2: wrap the valid suffix ending at i - 1.
            elif i >= 1:
                inner = dp[i - 1]
                candidate = i - inner - 1

                if candidate >= 0 and s[candidate] == '(':
                    dp[i] = inner + 2
                    if candidate >= 1:
                        dp[i] += dp[candidate - 1]

        best = max(best, dp[i])

    return best

The code stays close to the derivation:

• dp[i] answers the suffix-state obligation.
• inner records the valid suffix immediately before the current close.
• candidate identifies the only possible wrapping opening boundary.
• best handles the fact that the answer can end before the final character.

Python has a particularly dangerous edge case here: negative indices are legal. For example:

s[-1]

reads the last character rather than raising an error. That behavior is useful in normal Python code but incorrect for this recurrence. A conceptual index such as candidate = -1 means “no valid position,” not “the last character.”

Check every boundary before indexing:

if candidate >= 0 and s[candidate] == '(':

Likewise, only read dp[i - 2] when i >= 2, and only read dp[candidate - 1] when candidate >= 1.

Compare stack and two-pass scans

The DP solution is one linear-time approach, but it is not the only useful mental model.

Stack: explicit unmatched boundaries

A stack solution tracks indices of unmatched opening parentheses and a base index for the most recent unmatched closing parenthesis. When a close is matched, the distance back to the current boundary gives the length of the valid suffix.

Its invariant is boundary-oriented:

The stack top marks the position immediately before the current valid region or the position of an unmatched opening parenthesis.

The stack makes unmatched structure explicit. It runs in O(n) time and uses O(n) auxiliary space.

Two-pass scan: constant extra space

A two-pass counter scan tracks the number of opens and closes while moving left to right and then right to left. The two directions handle different barriers:

• A left-to-right pass detects too many closing parentheses.
• A right-to-left pass detects too many opening parentheses.

Together, they handle the unmatched boundary cases without storing a DP array or stack. The time is O(n) and the extra space is O(1).

The tradeoff is clarity of state. The scan is compact, but its correctness depends on understanding why opposite traversal directions repair the blind spot of a single pass.

My interview decision rule is simple:

• Choose DP when you want a reusable suffix recurrence or may extend the state later.
• Choose a stack when explicit unmatched-boundary tracking makes the reasoning easier to communicate.
• Choose the two-pass scan when constant extra space is the primary requirement.

Do not choose the shortest code before you can state its invariant. Short code with an invisible state model is difficult to debug under pressure.

Complexity and failure-focused tests

The DP algorithm performs constant-time work at each index:

• one or two character checks,
• a few arithmetic operations,
• constant-time array reads and writes.

Therefore:

Time:  O(n)
Space: O(n)

The O(n) space is the dp array. The input string is not counted as auxiliary space.

Test the recurrence against failure modes, not just friendly examples:

Category	Example	Expected result
Empty input	""	0
One character	"(" or ")"	0
All opens	"((("	0
All closes	")))"	0
One pair	"()"	2
Adjacent pairs	"()()"	4
Nested pair	"(())"	4
Nested and joined	"(()())"	6
Barrier before a region	")()())"	4
Internal maximum	"(()"	2
Valid span followed by a barrier	"())"	2

Pay particular attention to these index expressions:

i - 2
i - dp[i - 1] - 1
candidate - 1

Each one represents a different boundary:

• i - 2 is before an adjacent pair.
• i - dp[i - 1] - 1 skips over the valid suffix to find a possible wrapping opener.
• candidate - 1 is before that opener, where another valid block may join.

When debugging, print the index, character, inner, candidate, dp[i], and best. The failing state usually exposes the wrong boundary immediately.

The transferable pattern

When a string problem asks for the best valid suffix ending at each position, start with the suffix state:

What is the best valid region ending exactly here?

Then identify the boundary that can connect that suffix to earlier state.

For this problem:

1. A close can complete a valid suffix.
2. The previous DP value tells you how far that suffix reaches.
3. The computed boundary identifies a possible matching opener.
4. A preceding DP value joins adjacent valid regions.
5. A global maximum handles spans that end anywhere.

In an interview, write the state sentence and boundary arithmetic before coding. Then test one nested case, one adjacent-join case, and one barrier case. Read the error, trace the state, fix the assumption.