Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The input is a string made only of ( and ).

The task is not to check whether the whole string is valid. The task is to find the length of the longest contiguous substring that forms a valid parentheses expression.

That means two things matter:

  • the substring has to be balanced
  • every prefix inside that substring must also be valid, so it can never close more parentheses than it has opened

This is why the problem is trickier than just counting how many ( and ) characters exist.

Why brute force feels tempting but breaks down

A straightforward idea is to try every substring, check whether it is valid, and keep the maximum length.

That works, but there are O(n^2) substrings, and validating each one can take O(n), so the total work can reach O(n^3). Even with some pruning, that is much too slow for interview-sized inputs.

So the real goal is to scan once and keep just enough information to know where the current valid region could start.

The key insight

Whenever a ) appears, it wants to match the most recent unmatched ( before it.

That naturally suggests a stack of indices for unmatched opening parentheses.

The other important idea is to keep track of the most recent position that definitely cannot be part of a valid substring. A convenient way to do that is to place a sentinel index, initially -1, at the bottom of the stack.

Then the scan becomes simple:

  • when the current character is (, push its index
  • when the current character is ), pop one opening index
  • if the stack becomes empty, this ) is an unmatched closing parenthesis, so record its index as the new boundary
  • otherwise, the current valid substring starts right after the index now on top of the stack

That last point is the whole trick. If the top of the stack is the last unmatched boundary, then current_index - stack[-1] is exactly the length of the longest valid substring ending at the current position.

Optimal solutions to know

There are two linear-time solutions worth knowing in interviews.

The most direct one is the stack solution. It runs in O(n) time and uses O(n) extra space in the worst case. It is usually the easiest to derive and explain because the stack mirrors the matching behavior of parentheses.

There is also a two-pass counter solution that runs in O(n) time and O(1) extra space. Scan left to right counting opens and closes. When they are equal, update the answer. When closes exceed opens, reset. Then scan right to left to catch cases with too many unmatched opens. That version is elegant and space-efficient, but the stack method is often easier to reason about during the first pass of an interview.

How to derive the stack solution

Start from the observation that valid parentheses behave like matching pairs. If the current character is (, it may help a future substring, so keep its index. If the current character is ), try to match it with the latest unmatched (.

Now consider what happens after a successful match. The current character may end a valid substring, but that substring might stretch farther left than the matched (. It can extend all the way back to the position after the most recent unmatched boundary. That is why storing indices, rather than just counts, matters.

The sentinel -1 gives the first valid substring a boundary before the string starts. Later, if an unmatched ) appears, its index becomes the new boundary because no valid substring can cross it.

Once that boundary idea is clear, the length formula becomes obvious:

current_index - last_invalid_boundary

The stack stores that boundary for free.

Python solution

from typing import List


def longest_valid_parentheses_length(parentheses: str) -> int:
    """
    Return the length of the longest contiguous valid parentheses substring.

    The stack stores indices. Its top always represents the index just before the
    start of the current valid region:
    - unmatched opening parentheses stay on the stack
    - unmatched closing parentheses reset the boundary
    """
    unmatched_boundaries: List[int] = [-1]
    longest_length = 0

    for current_index, character in enumerate(parentheses):
        if character == "(":
            unmatched_boundaries.append(current_index)
            continue

        # Try to match this closing parenthesis with the latest unmatched "(".
        unmatched_boundaries.pop()

        if not unmatched_boundaries:
            # No opening parenthesis was available, so this index is a hard reset.
            unmatched_boundaries.append(current_index)
            continue

        current_valid_length = current_index - unmatched_boundaries[-1]
        longest_length = max(longest_length, current_valid_length)

    return longest_length


class Solution:
    def longestValidParentheses(self, s: str) -> int:
        """LeetCode entry point."""
        return longest_valid_parentheses_length(parentheses=s)

This runs in O(n) time because each index is pushed and popped at most once. The extra space is O(n) in the worst case when the string contains many unmatched opening parentheses.

Interview follow-ups

Can this be done with O(1) extra space?

Yes. Use the two-pass counting method. In the left-to-right pass, count how many ( and ) characters have been seen. When the counts are equal, the current prefix ends in a valid substring and its length is 2 * close_count. If closing parentheses ever outnumber opening parentheses, reset both counters because no valid substring can cross that point. Then repeat from right to left, reversing the reset condition to handle cases with too many unmatched opening parentheses. This works because a balanced segment must have equal counts, and the two scan directions together catch both kinds of imbalance. The tradeoff is that this method is less obvious than the stack solution and does not naturally return substring boundaries.

How would you return the actual substring, not just its length?

Keep the same stack logic, but whenever a better answer is found, also store the start and end indices. The end is the current index. The start is stack[-1] + 1 after the successful match, because the stack top is the boundary just before the valid substring begins. This works for the same reason the length formula works: the boundary index is the closest unmatched position to the left. The complexity remains O(n) time and O(n) space, but the implementation carries a little more state.

How would you solve it with dynamic programming?

Let dp[i] be the length of the longest valid substring ending exactly at index i. Only positions containing ) can finish a valid substring. If s[i - 1] is (, then a new pair () closes and dp[i] = dp[i - 2] + 2. If s[i - 1] is ) and there is a matching ( just before the previous valid block, then dp[i] = dp[i - 1] + 2 + dp[matching_index - 1]. This works because each case extends the longest valid substring that ends immediately before the new match. The complexity is still O(n) time, with O(n) extra space. The tradeoff is that DP is more algebraic and usually harder to derive on the spot than the stack approach.

What changes if the string can include other bracket types such as [] and {}?

Then the stack should store indices or characters for opening brackets, and every closing bracket must match the correct opening type. The same boundary idea still works: an unmatched closing bracket resets the boundary, while a successful type-correct match can extend a valid region. This works because nested bracket languages are still driven by last-opened, first-closed structure, which is exactly what a stack models. The tradeoff is that the matching rule is slightly richer, but the overall time remains O(n) and the space remains O(n).