Understanding the Problem

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 key word here is "contiguous" -- we're looking for a substring, not a subsequence. We can't skip characters.

What makes this tricky is that valid parentheses can be adjacent or nested. For example, in ()((), there are two valid portions: () at the start and () inside the second group, but the longest contiguous valid substring is just () with length 2. Meanwhile, (())() is entirely valid with length 6. So the challenge is figuring out where valid substrings start and end, especially when they chain together.

The key observation: an unmatched parenthesis acts as a "barrier" that separates valid regions. If we can identify these barriers, we can measure the lengths of valid regions between them.

Key Constraints:

0 <= s.length <= 3 * 10^4 -- We can afford up to O(n^2), but O(n) is ideal. O(n) stack or two-pass solutions are what interviewers expect for a Hard problem.
s[i] is '(' or ')' -- Only two characters to handle. No other characters to worry about.
String can be empty -- We need to handle the empty string edge case (return 0).

Approach 1: Brute Force

Intuition

The most straightforward approach: check every possible substring and see if it forms valid parentheses. For each starting index, try every possible ending index, and validate whether that substring is a well-formed parentheses sequence. Track the longest one found.

To check if a substring is valid, we can use a simple counter. Walk through the substring, incrementing for ( and decrementing for ). If the counter ever goes negative, the substring is invalid (too many closing parens). If it ends at zero, the substring is valid.

Algorithm

For each starting index i from 0 to n-1, do the following:
For each ending index j from i+2 to n (step by 2, since valid parentheses always have even length):
Check if the substring s[i..j] is valid by scanning with a counter.
If valid, update the maximum length.
Return the maximum length found.

Example Walkthrough

Input:

Inputs=)()())

)

(

)

(

)

We check all substrings: )( is invalid, )() is invalid, () at indices 1-2 is valid (length 2), ()() at indices 1-4 is valid (length 4), )()()) is invalid. The longest valid substring is ()() with length 4.

Output:

Output4

Code

Complexity Analysis

Time Complexity: O(n^3). We check O(n^2) substrings, and validating each one takes O(n) time.
Space Complexity: O(1). We only use a counter variable and loop indices.

For every starting index, we're re-scanning overlapping substrings from scratch. What if we could determine the longest valid substring ending at each position in a single pass, building on results we've already computed?

Approach 2: Dynamic Programming

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, we just return its maximum value.

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

Direct match: If s[i-1] = '(', then these two characters form (). The valid length is 2 + dp[i-2] (the 2 from this pair, plus whatever valid substring ended just before it).

Wrapping match: If s[i-1] = ')' and there's already a valid substring ending at i-1, then we need to look past that valid substring. If s[i - dp[i-1] - 1] = '(', that opening paren matches our closing paren at i. The length becomes dp[i-1] + 2 + dp[i - dp[i-1] - 2] (the inner valid part, the new matching pair, plus any valid part before the opening paren).

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

Why does this work?

The DP recurrence captures both ways a valid substring can end at position i. When s[i-1]='(', we have a direct () pair. When s[i-1]=')', there might be a valid block before position i that we need to "jump over" to find the matching ( for our ). The beauty is that dp[i-1] tells us exactly how far to jump. And once we find a match, we also add dp[matchIdx-1] to concatenate with any valid substring that came right before our matching (.

Algorithm

Create an array dp of size n, initialized to 0.
Iterate from index 1 to n-1 (index 0 can never end a valid substring by itself):

a. If s[i] = ')' and s[i-1] = '(', set dp[i] = 2 + (i >= 2 ? dp[i-2] : 0).

b. If s[i] = ')' and s[i-1] = ')', check the character at position i - dp[i-1] - 1. If that's '(', set dp[i] = dp[i-1] + 2 + (i - dp[i-1] >= 2 ? dp[i - dp[i-1] - 2] : 0).

Return the maximum value in dp.

Example Walkthrough

1Initialize: dp = [0, 0, 0, 0, 0], scan from i=1

(

)

(

)

1/5

1dp initialized to all zeros

1/5

Code

Complexity Analysis

Time Complexity: O(n). Single pass through the string, doing O(1) work at each index.
Space Complexity: O(n). The dp array uses O(n) extra space.

The DP approach is O(n) time but uses O(n) space. Can we find a solution that uses only O(1) extra space?

Approach 3: Stack

Intuition

Every unmatched parenthesis acts as a boundary between valid regions. If we could find the indices of all unmatched parentheses, the longest valid substring would be the longest gap between consecutive unmatched indices.

A stack gives us a clean way to find these boundaries. We push indices onto the stack. When we see a ) that matches a ( on the stack, we pop. Whatever remains on the stack after processing the whole string are the unmatched positions. But we don't even need to wait until the end -- we can compute the answer as we go.

The trick: start with -1 on the stack as a "base" boundary. When we pop a matching (, the current valid length is i - stack.peek(). If we pop and the stack is empty, push the current index as the new base boundary (because this ) is unmatched).

Why does this work?

The stack always holds the indices of unmatched parentheses (plus the base boundary). When we successfully match a pair, the top of the stack is the nearest unmatched position to the left. The distance from that position to our current index is exactly the length of the valid substring ending here. The -1 base handles the case where the valid substring starts at index 0.

Algorithm

Initialize a stack with -1 (the base boundary).
For each index i in the string:

a. If s[i] = '(', push i onto the stack.

b. If s[i] = ')', pop from the stack.

If the stack is now empty, push i (new base boundary).
Otherwise, update max length as i - stack.peek().

Return the maximum length.

Example Walkthrough

1Initialize: stack=[-1], max=0

(

)

(

)

1/7

1Stack initialized with base boundary -1

-1

Top

1/7

Code

Complexity Analysis

Time Complexity: O(n). Single pass through the string. Each index is pushed and popped at most once.
Space Complexity: O(n). In the worst case (all opening parentheses), the stack holds n+1 elements.

Both the DP and stack approaches use O(n) space. What if we could solve this with just a few counter variables?

Approach 4: Two-Pass Counting (Optimal)

Intuition

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

Scan left to right. Maintain two counters: open and close. Every time they're equal, we have a valid substring of length open + close. When close > open, the substring is broken, so reset both to 0.

But this misses cases like "(()". Scanning left to right, open stays ahead of close and they never equalize, even though there's a valid () of length 2 inside. The fix: do a second pass from right to left, this time resetting when open > close. Together, the two passes catch every valid substring.

Why does this work?

The left-to-right pass catches every valid substring that ends with close > open somewhere to its left. But it misses valid substrings where there are excess ( that never get matched, because open stays strictly greater than close throughout. In those cases, looking from the right side reveals the valid portion, because the excess ) on the right triggers resets, and the valid interior gets counted. Together, the two passes guarantee that no valid substring is missed.

Algorithm

Initialize open = 0, close = 0, maxLen = 0.
Left-to-right pass: increment open for (, close for ). When equal, update max. When close > open, reset.
Reset counters. Right-to-left pass: same logic but reset when open > close.
Return maxLen.

Example Walkthrough

1Left-to-Right: i=0 ')' → close>open, reset

)

(

)

(

)

1/6

Code

Complexity Analysis

Time Complexity: O(n). Two passes through the string, each doing O(1) work per character.
Space Complexity: O(1). Only uses a fixed number of integer variables regardless of input size.

Longest Valid Parentheses

Understanding the Problem

Key Constraints:

Approach 1: Brute Force

Intuition

Algorithm

Example Walkthrough

Code

Approach 2: Dynamic Programming

Intuition

Algorithm

Example Walkthrough

Code

Approach 3: Stack

Intuition

Algorithm

Example Walkthrough

Code

Approach 4: Two-Pass Counting (Optimal)

Intuition

Algorithm

Example Walkthrough

Code

Get Premium