Skip to main content

92. Longest Valid Parentheses

hardAsked at Reddit

Find the length of the longest valid parentheses substring. Reddit uses this stack-based DP problem to test sophisticated index tracking — the same shape used when validating longest valid markdown nesting in user input.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit on-site stack/DP hard.

Problem

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

Constraints

  • 0 <= s.length <= 3 * 10^4
  • s[i] is '(', or ')'.

Examples

Example 1

Input
s = "(()"
Output
2

Explanation: "()".'

Example 2

Input
s = ")()())"
Output
4

Explanation: "()()".'

Example 3

Input
s = ""
Output
0

Approaches

1. Two-pass counter

Left-to-right: count '(' and ')'. When balanced, update max. Reset on ')' overflow. Repeat right-to-left.

Time
O(n)
Space
O(1)
function longestValidParentheses(s) {
  let left = 0, right = 0, max = 0;
  for (const ch of s) {
    if (ch === '(') left++; else right++;
    if (left === right) max = Math.max(max, 2 * left);
    else if (right > left) left = right = 0;
  }
  left = right = 0;
  for (let i = s.length - 1; i >= 0; i--) {
    if (s[i] === '(') left++; else right++;
    if (left === right) max = Math.max(max, 2 * right);
    else if (left > right) left = right = 0;
  }
  return max;
}

Tradeoff: O(1) space — clever counter approach.

2. Stack of indices (optimal teaching version)

Push -1 as base. On '(', push index. On ')', pop; if stack empty push current index as new base; else max = i - stack.top().

Time
O(n)
Space
O(n)
function longestValidParentheses(s) {
  const stack = [-1];
  let max = 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);
      else max = Math.max(max, i - stack[stack.length - 1]);
    }
  }
  return max;
}

Tradeoff: Clearer to explain. O(n) memory.

Reddit-specific tips

Reddit interviewers want the stack version because it's easier to reason about. Bonus signal: mention the two-pass counter for O(1) space and discuss when each is preferred.

Common mistakes

  • Forgetting to seed the stack with -1 (boundary marker).
  • Resetting on left > right (only reset when ')' goes excess).
  • Counting individual ')' instead of using the boundary trick.

Follow-up questions

An interviewer at Reddit may pivot to one of these next:

  • Valid parentheses (LC 20).
  • Generate parentheses (LC 22).
  • Number of valid parentheses substrings.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why seed the stack with -1?

It marks the 'before the start' boundary so that i - stack.top() gives a length when the entire prefix is valid.

Why the two-pass approach?

Single left-to-right pass fails on '(()'. Right-to-left catches the missing case.

Practice these live with InterviewChamp.AI

Drill Longest Valid Parentheses and other Reddit interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →