Longest Valid Parentheses

You are given a string s made only of the characters '(' and ')'.

A string is well-formed if every opening bracket can be paired with a later closing bracket so that the pairs nest properly, for example "(())" or "()(())". Find the longest contiguous substring of s that is well-formed and return its length. Return 0 if there is none (including when s is empty).

Example 1

Example 2

Example 3

Constraints

• 0 <= s.length <= 3 × 104
• s[i] is '(' or ')'.

Pattern Path · Stacks · problem 51 of 169

Start simple

Check every substring of even length with a counter to see if it is well-formed: O(n³), or O(n²) if you extend each start point one character at a time.

The key idea

Scan the string once and keep a stack of indices. Everything on the stack is a position that is not yet part of a matched pair: opening brackets still waiting for a partner, and, at the very bottom, a boundary marking the last spot that no valid substring can cross.

Start with -1 as the boundary, meaning "just before the string". For an opening bracket, push its index. For a closing bracket, pop: that removes the opening bracket it matches. Now look at the stack. If it is empty, this ')' had no partner, so it becomes the new boundary. Otherwise, everything strictly between the index on top of the stack and i is fully matched, because any unmatched character in that range would still be on the stack above it. That gives a valid substring of length i - top ending at i.

This naturally handles both nested pairs, like "(())", and concatenated ones, like "()()": concatenation works because matched pairs leave no trace, so the earlier boundary stays put. A dynamic programming solution (dp[i] = longest valid substring ending at i) or a two-pass counter scan also run in O(n).

Complexity

• Time: O(n)
• Space: O(n)

Python

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # Bottom of the stack: the index just before the current valid stretch.
        # Above it: indices of '(' still waiting for a partner.
        stack = [-1]
        best = 0
        for i, ch in enumerate(s):
            if ch == "(":
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)  # unmatched ')': nothing valid can cross it
                else:
                    best = max(best, i - stack[-1])
        return best

JavaScript

var longestValidParentheses = function(s) {
  // Bottom of the stack: the index just before the current valid stretch.
  // Above it: indices of '(' still waiting for a partner.
  const stack = [-1];
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(") {
      stack.push(i);
    } else {
      stack.pop();
      if (stack.length === 0) {
        stack.push(i); // unmatched ')': nothing valid can cross it
      } else {
        best = Math.max(best, i - stack[stack.length - 1]);
      }
    }
  }
  return best;
};

What the interviewer is checking

The interviewer is looking for the step from "is this string valid?" to "how long is the valid run ending here?", and whether you store positions rather than characters on the stack.

Mistakes to avoid

• Counting matched pairs overall (e.g. returning 4 for "()(()") instead of the longest contiguous valid stretch.
• Forgetting the initial -1 sentinel, which miscounts a valid prefix.
• Not resetting the boundary on an unmatched ')'.
• A single left-to-right counter scan misses cases like "(()"; it needs a right-to-left pass too.

Follow-ups to expect

• Can you do it in O(1) extra space? (Two counter passes, left and right.)
• Return the substring itself. (Remember the start index of the best run.)
• What if there are several bracket types? (Stack must also check the bracket kind.)

In real software

Editors and linters use the same index stack to highlight the largest correctly balanced region of code when brackets are broken, so they can recover and keep parsing around the error.

Practice next