Longest Valid Parentheses: Stack-Based Substring Tracking

Longest Valid Parentheses is LeetCode problem 32, rated Hard. Given a string containing only ( and ), return the length of the longest valid (well-formed) parentheses substring.

Examples:

• "(()" returns 2 (the valid substring is "()")
• ")()())" returns 4 (the valid substring is "()()")
• "" returns 0

This is not about checking whether the whole string is valid. It is about finding the longest contiguous chunk that is. That shift from yes/no validation to "find the longest" is what makes this problem tricky, and what makes it a great exercise in index-based stack tracking.

Why a stack of indices

If you have solved Valid Parentheses, you know the basic pattern: push opening brackets, pop when you see a closing bracket. But that problem only needs a yes/no answer. Here, you need to measure the length of valid substrings, and the key insight is that the stack should store indices, not characters.

When you encounter ) and the stack is not empty, you pop the top (the index of the matching (). The length of the current valid substring is then i - stack[-1], where stack[-1] is the new top after popping. That top acts as the left boundary of the current valid region.

To make this formula work even for the first match, you initialize the stack with -1. That way, if you match the very first ( in the string, the length calculation i - (-1) gives the correct answer.

If you pop and the stack becomes empty, there is no left boundary, meaning the current ) is unmatched. Push its index as the new boundary for future calculations.

The algorithm step by step

1. Initialize a stack with [-1].
2. For each character at index i:
   • If it is (, push i onto the stack.
   • If it is ), pop the top. Then:
     • If the stack is empty, push i (new boundary).
     • If the stack is not empty, compute length = i - stack[-1] and update the maximum.
3. Return the maximum length.

Visual walkthrough

Let's trace through ")()())" step by step. Watch how the stack manages boundaries and how the length formula i - stack[-1] captures both nested and consecutive valid substrings.

Notice how at step 5, the length jumps to 4 even though the two pairs () at indices 1-2 and () at indices 3-4 are consecutive, not nested. The stack handles this correctly because after both pairs are matched, the boundary at stack[-1] is still index 0, so the formula gives 4 - 0 = 4. This is why storing indices instead of characters is so powerful.

The code

Here is the Python solution using the stack-based approach:

def longestValidParentheses(s: str) -> int:
    stack = [-1]
    max_len = 0

    for i, ch in enumerate(s):
        if ch == "(":
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                max_len = max(max_len, i - stack[-1])

    return max_len

The entire logic fits in a single pass. For each ), you pop, then either set a new boundary (if the stack emptied) or measure the valid substring length (if the stack still has entries). The max_len accumulator tracks the best result seen so far.

The DP approach (briefly)

There is also a dynamic programming solution. Define dp[i] as the length of the longest valid substring ending at index i. If s[i] == "(", then dp[i] = 0 because no valid substring ends with an open paren. If s[i] == ")", you check:

• If s[i-1] == "(", then dp[i] = dp[i-2] + 2 (extends a pair).
• If s[i-1] == ")" and s[i - dp[i-1] - 1] == "(", then dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2] (closes a nested group and connects to any valid substring before it).

The DP approach also runs in O(n) time and O(n) space. It is worth knowing, but the stack approach is easier to recall under pressure because the logic is more linear. You do not need to reason about nested index arithmetic.

Complexity analysis

Time: O(n). You iterate through the string once. Each character triggers at most one push and one pop, both O(1). Total work is proportional to the length of the string.

Space: O(n). In the worst case (e.g., "((((("), every character gets pushed onto the stack. The stack can grow up to n + 1 entries (including the initial -1).

Edge cases

These are the inputs that expose bugs in incorrect implementations:

• Empty string. Return 0. The loop does not execute, and max_len stays at 0.
• All opening parens ("((("). Nothing ever matches, so max_len stays at 0. The stack fills up with indices but never triggers a length calculation.
• All closing parens (")))"). Each ) pops the current boundary and pushes itself as the new boundary. No valid substring is found. Return 0.
• Nested valid substring ("(())"). The inner pair matches first, then the outer pair matches. At the end, length = 3 - (-1) = 4. The stack correctly handles nesting.
• Consecutive valid substrings ("()()"). The first pair matches with length 2, then the second pair matches. Because the boundary stays at -1, the second match gives length = 3 - (-1) = 4. Consecutive pairs merge into one long valid substring.
• Mixed ("()(()"). The () at indices 0-1 is valid (length 2). The (( at indices 2-3 has one unmatched paren. The ) is missing. Answer is 2.

The building blocks

This problem is built from two reusable building blocks that show up across many LeetCode problems.

Index-based stack tracking

Instead of pushing characters onto the stack, you push their indices. This lets you calculate distances, lengths, and positions after a match. The same technique appears in:

• Daily Temperatures (LeetCode 739): push indices onto a monotonic stack, compute the gap when you find a warmer day
• Largest Rectangle in Histogram (LeetCode 84): push bar indices, calculate width using the difference between indices after popping
• Trapping Rain Water (LeetCode 42): push indices to track boundaries of trapped water regions

The pattern is always: push the index, pop when a condition is met, then use i - stack[-1] (or similar arithmetic) to compute the relevant measurement.

Valid substring length calculation

The formula length = i - stack[-1] after popping is specific to parentheses matching, but the general idea of using a sentinel value as a boundary marker is broadly useful. Initializing with -1 (or the equivalent) avoids special-casing the start of the input. You will see this technique whenever you need to track "where the current valid region started."

From understanding to recall

You see how the stack tracks boundaries. You understand that i - stack[-1] gives the length. You know the sentinel -1 eliminates edge cases at the start. But in an interview, can you write this from scratch in under three minutes?

The details matter. Is the sentinel -1 or 0? Do you pop before or after checking if the stack is empty? Do you push the index of ) or ( when the stack empties? These small decisions are where people freeze. Not because they do not understand the algorithm, but because recognition and recall are different skills.

Spaced repetition bridges that gap. You type the solution from memory at increasing intervals. After a few cycles, the initialization, the pop-then-check flow, and the length formula become automatic. You do not reconstruct the logic during an interview. You just write it.

Related posts

• Valid Parentheses - The foundational stack-matching problem. Longest Valid Parentheses extends the same push/pop pattern but adds index tracking to measure substring lengths.
• Generate Parentheses - Builds valid parentheses strings from scratch using backtracking. A different direction from the same parentheses family: construction instead of analysis.