Longest Valid Parentheses Solution

Problem

Given a string made up entirely of ( and ) characters, find the length of the longest contiguous substring that forms a valid (properly matched) parentheses sequence. A single unmatched ) or a dangling ( breaks the sequence.

Input: s = ")()())"
Output: 4
Explanation: The substring "()()" at indices 1–4 is the longest valid piece.

Counter-example: s = "(((" → 0, because no closing parentheses exist to form any matched pair.

Intuition

Any unmatched ) acts like a wall — no valid sequence can cross it. The challenge is efficiently tracking where each wall is so you can measure the gap between them. A stack of indices lets you do exactly that: the bottom of the stack always holds the index of the most recent unmatched character, so whenever a ) closes a (, the length is just current_index - stack_top.

Approach 1 — Stack

Use a stack to track indices of unmatched characters. A sentinel value of -1 starts on the stack as the left boundary, so the first valid close immediately yields the correct length without a special case.

Initialize stack = [-1] and max_length = 0.
Iterate over each character with its index.
If (: push its index onto the stack.
If ): pop the top. If the stack is now empty, push the current index as the new left boundary (this ) is unmatched). Otherwise, the valid substring length is current_index - stack.top().
Update max_length after each successful match.
Return max_length.

1def longestValidParentheses(s: str) -> int:
2    stack = [-1]  # sentinel: left boundary before the string starts
3    max_length = 0
4
5    for i, char in enumerate(s):
6        if char == '(':
7            stack.append(i)
8        else:
9            stack.pop()
10            if not stack:
11                stack.append(i)  # unmatched ')' becomes new left boundary
12            else:
13                max_length = max(max_length, i - stack[-1])
14
15    return max_length

Time: O(n) — single pass through the string.
Space: O(n) — in the worst case (all () the stack holds every index.

Approach 2 — Two-Pass Counter

Scan the string twice using only two integer counters, achieving constant space. A left-to-right pass catches sequences that end with balanced ), and a right-to-left pass catches sequences that start with balanced (.

Left to right: count left_count and right_count. When equal, update max_length = 2 * right_count. When right_count > left_count, reset both to zero (unmatched ) breaks the run).
Reset both counters to zero.
Right to left: count the same way but reset when left_count > right_count.
Return max_length.

1def longestValidParentheses(s: str) -> int:
2    max_length = 0
3    left_count = right_count = 0
4
5    for char in s:
6        if char == '(':
7            left_count += 1
8        else:
9            right_count += 1
10        if left_count == right_count:
11            max_length = max(max_length, 2 * right_count)
12        elif right_count > left_count:
13            left_count = right_count = 0  # unmatched ')' breaks the sequence
14
15    left_count = right_count = 0
16
17    for char in reversed(s):
18        if char == '(':
19            left_count += 1
20        else:
21            right_count += 1
22        if left_count == right_count:
23            max_length = max(max_length, 2 * left_count)
24        elif left_count > right_count:
25            left_count = right_count = 0  # unmatched '(' breaks the reverse sequence
26
27    return max_length

Time: O(n) — two linear passes.
Space: O(1) — only two integer counters beyond the input.

Complexity Summary

Approach	Time	Space	When to use
Stack	O(n)	O(n)	Clearest to reason about; good default choice
Two-Pass Counter	O(n)	O(1)	When memory is a hard constraint

Common Mistakes

Not seeding the stack with -1 — without this sentinel, the very first valid close "()" pops index 0 from the stack, leaves it empty, and you push 0 as a new boundary instead of computing length 2; the whole calculation breaks.
Only doing the left-to-right pass in Approach 2 — "(()" has left_count=2, right_count=1 at the end, so the counters never equalize and the valid "()" is missed entirely; the reverse pass catches it.
Thinking adjacent valid substrings count separately — "()()" is one valid run of length 4, not two runs of length 2; the stack approach naturally merges adjacent sequences because the boundary index never resets between them.
Pushing the character instead of its index — stack.append(char) gives you '(' or ')', which makes i - stack[-1] a type error; you need the index to compute the distance to the last unmatched boundary.
Forgetting the symmetric reset condition in the reverse pass — in the left-to-right pass you reset when right_count > left_count; in the reverse pass you must reset when left_count > right_count, not the same direction.

Longest Valid Parentheses — Solution