Skip to main content

95. Longest Valid Parentheses

hardAsked at Datadog

Find the length of the longest valid (well-formed) parentheses substring. Datadog uses this for the stack-tracking-indices trick — same shape as their balanced-segment detector on partially-corrupted log streams.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite hard problem.

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 valid substring ending at i.

Time
O(n)
Space
O(n)
// dp[i] = if s[i] == ')': if s[i-1] == '(', dp[i-2] + 2; if s[i-1] == ')' and s[i-dp[i-1]-1] == '(', dp[i-1] + 2 + dp[i-dp[i-1]-2].

Tradeoff: Works but the recurrence is error-prone.

2. Stack with index tracking (optimal)

Stack starts with -1. Push i on '('. On ')', pop; if stack empty, push i; else update best with 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: Single pass. Stack holds 'last invalid' index; valid runs measured from it. Datadog-canonical.

Datadog-specific tips

Datadog grades on the -1 sentinel and the 'push i on unbalanced )' trick. Articulate why: stack always holds the index BEFORE the current valid run; valid length = i - stack.top().

Common mistakes

  • Forgetting the -1 sentinel — first valid pair misses length.
  • Resetting stack to empty on unbalanced ) — fail.
  • Counting open parens instead of indices — can't recover the SPAN.

Follow-up questions

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

  • Valid Parentheses (LC 20) — base case.
  • Generate Parentheses (LC 22) — different problem.
  • Datadog-style: balanced-segment detector on partially-corrupted streams.

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

Without it, the first valid pair's length couldn't be measured (no 'before' index).

Why push i on unbalanced )?

It establishes the new 'before' anchor for future valid runs.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →