Skip to main content

86. Longest Valid Parentheses

hardAsked at Snowflake

Find the longest valid parentheses substring. Snowflake asks this for stack-with-index — relevant to recovering nesting depth during SQL parser error reporting.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler-team uses this to set up SQL-parser error-recovery.
  • LeetCode Discuss (2025-10)— Reported at Snowflake SDE-II screens.

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

Example 2

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

Example 3

Input
s = ""
Output
0

Approaches

1. DP

dp[i] = length of longest valid string ending at i. Transitions depend on s[i] and the matching '('.

Time
O(n)
Space
O(n)
// outline — DP works but stack version is more intuitive.

Tradeoff: Works but transitions are subtle.

2. Stack of indices (optimal)

Initialize stack with -1 (sentinel). On '(': push i. On ')': pop. If stack empty, push i; else current length = i - stack.top.

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

Tradeoff: Linear, single pass. The -1 sentinel handles 'no preceding unmatched ('' case uniformly.

Snowflake-specific tips

Snowflake interviewers want the sentinel-index pattern stated. Bonus signal: connect to SQL parser error recovery — when an unmatched bracket appears mid-query, the parser uses the stack-of-indices pattern to skip back to the last valid token.

Common mistakes

  • Initializing stack empty — fails the first ')' case.
  • Pushing index of ')' on every mismatch instead of using as new base — loses the boundary.
  • Computing length as i+1 instead of i - stack.top — wrong because the base might not be -1.

Follow-up questions

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

  • Longest Valid Parentheses with multiple bracket types.
  • Two-pass O(1) space solution (forward + backward counts).
  • How does Snowflake's parser recover from bracket mismatches?

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 the -1 sentinel?

It marks the base from which to measure. When the first valid segment closes, length = i - (-1) = i + 1 — correct.

When do we replace the sentinel?

On a ')' with empty stack — the unmatched ')' becomes the new base for subsequent matches.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →