We need to find the length of the longest contiguous substring that forms a valid sequence of parentheses. A valid sequence means every ( has a matching ), and they're properly nested. The word "contiguous" matters: we're looking for a substring, not a subsequence, so we can't skip characters.

Valid parentheses can be adjacent or nested, which is what makes the problem harder than simple validation. In ()((), there are two valid portions, () at the start and () inside the second group, but the longest contiguous valid substring is () with length 2. In (())(), the entire string is valid with length 6. The challenge is figuring out where valid substrings start and end, especially when they chain together.

One property drives every efficient solution: an unmatched parenthesis acts as a barrier that separates valid regions. If we can locate these barriers, the answer is the longest stretch of matched characters between them.

Key Constraints:

Intuition

Check every possible substring and see if it forms valid parentheses. For each starting index, try every ending index, validate whether that substring is well-formed, and track the longest one found.

To check validity, walk through the substring with a counter, incrementing for ( and decrementing for ). If the counter ever goes negative, the substring has more closing than opening parens at some prefix, so it is invalid. If it ends at zero, the substring is valid. Since a valid sequence always has even length, we only test even-length substrings.

Algorithm

Example Walkthrough

Input:

We test even-length substrings starting at each index. Starting at index 0, every substring begins with ), so the counter goes negative immediately and none are valid. Starting at index 1, () (indices 1-2) is valid with length 2, and ()() (indices 1-4) is valid with length 4. The substring ()()) is odd-length so we skip it, and ()() followed by the trailing ) would be )()()) from index 0, already rejected. Starting at index 3, () (indices 3-4) is valid with length 2. No other start index yields anything longer. The longest valid substring is ()() with length 4.

Output:

Code

The cubic cost comes from re-scanning overlapping substrings from scratch. The next approach computes the longest valid substring ending at each position in a single pass, reusing the results it has already computed.

Intuition

Define dp[i] as the length of the longest valid parentheses substring that ends at index i. If we can fill this array in one pass, the answer is its maximum value.

A ) at index i can form a valid substring in two ways:

If s[i] = '(', then dp[i] = 0 because no valid substring can end with an opening paren.

The wrapping case relies on dp[i-1] being a contiguous valid block ending exactly at i-1. That block spans indices i - dp[i-1] through i-1, so the character right before it sits at i - dp[i-1] - 1. If that character is (, it pairs with the ) at i and wraps the entire block, which is why we add dp[i-1] + 2. The final dp[matchIdx-1] term stitches on any valid substring that ended just before the wrapping (, handling chains like ()(()).

Algorithm

Example Walkthrough

Trace (()), which exercises both cases of the recurrence. Index 2 closes the inner pair through the direct case: s[2] = ')', s[1] = '(', so dp[2] = 2 + dp[0] = 2. Index 3 is the wrapping case: s[3] = ')' follows another ), and dp[2] = 2, so the match index is 3 - 2 - 1 = 0, where s[0] = '(' matches. That gives dp[3] = dp[2] + 2 = 4, since there is no valid block before index 0. The maximum over the array is 4.

Code

The DP approach runs in O(n) time but uses O(n) space for the array. The stack approach reaches the same time bound while making the barrier idea explicit, tracking the positions of unmatched parentheses directly.

Intuition

Every unmatched parenthesis acts as a boundary between valid regions, so the longest valid substring is the longest gap between consecutive unmatched indices. A stack lets us track these boundaries as we scan, instead of waiting until the end.

The stack holds the indices of parentheses that are still unmatched, plus one base boundary at the bottom. We push the index of every (. When we see a ), we pop, since that ) matches the most recent unmatched (. After the pop, the new top of the stack is the nearest unmatched position to the left, so the valid substring ending at the current index i has length i - stack.peek().

The base boundary handles the start of a valid region. We seed the stack with -1 so that a valid substring beginning at index 0 measures correctly. When a ) has nothing to match (the stack becomes empty after popping), that ) is itself unmatched, so we push its index as the new base boundary for everything that follows.

Algorithm

Example Walkthrough

Trace (()(). The leading ( at index 0 is never matched, so it stays on the stack and serves as the boundary for the two valid pairs to its right. When index 2 pops index 1, the top is 0, giving length 2 - 0 = 2. When index 4 pops index 3, the top is still 0, giving length 4 - 0 = 4. The answer is 4.

Code

Both the DP and stack approaches use O(n) space. The final approach drops that to O(1) by replacing the stack with two counters and a second scan.

Intuition

Instead of storing indices or DP values, count opening and closing parentheses as we scan.

Scan left to right with two counters, open and close. When they are equal, the characters since the last reset form a valid substring of length open + close. When close > open, there are too many closing parens, so reset both to 0 and start fresh.

This single pass misses cases like "(()". Scanning left to right, open stays ahead of close and the two counters never equalize, even though () of length 2 sits inside. A second pass from right to left fixes this, resetting when open > close instead. The two passes together catch every valid substring.

Algorithm

Example Walkthrough

Trace ((), the case that needs both passes. The left-to-right pass keeps open ahead of close the whole way and never records a match, so it returns 0. The right-to-left pass starts from the trailing ), equalizes the counters at the () in the middle, and records length 2 before the leading ( triggers a reset.

Code