32. Longest Valid Parentheses

Q: Why is the stack solution often easier to communicate?

Because the invariant 'stack holds the base index just before the current valid window' is easy to state and easy to verify against examples. The DP version's two-case recurrence is correct but harder to talk through under interview pressure.

Q: Is the two-counter O(1)-space solution worth learning?

Yes for follow-ups. Scan left-to-right tracking open and close counts; reset both when close > open; record length when they're equal. Scan right-to-left for the symmetric case. Total O(n) time, O(1) space.

hardAsked at Netflix

Given a string with only '(' and ')', return the length of the longest valid (well-formed) parentheses substring. Netflix asks this for the dynamic-programming round; the trick is the dp[i] recurrence using the character at i-1 to find the matching '('.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Netflix loops.

Glassdoor (2026-Q1)— Netflix L4-equivalent onsite reports describe this as the DP round on the algorithms loop.
Blind (2025-09)— Recurring in Netflix senior IC reports as the 'hard string' 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

Explanation: The longest valid substring is "()".

Example 2

Input

s = ")()())"

Output

Explanation: The longest valid substring is "()()".

Example 3

Input

s = ""

Output

Approaches

1. Brute-force every substring

For each (i, j) substring, check validity with a counter; track the longest valid length.

Time: O(n^3)
Space: O(1)

function longestValidBrute(s) {
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    for (let j = i + 2; j <= s.length; j += 2) {
      let bal = 0, ok = true;
      for (let k = i; k < j; k++) {
        bal += s[k] === '(' ? 1 : -1;
        if (bal < 0) { ok = false; break; }
      }
      if (ok && bal === 0) best = Math.max(best, j - i);
    }
  }
  return best;
}

Tradeoff: TLEs at n = 30000 (2.7 * 10^13 ops in the worst case). Useful only to set up the better approaches.

2. Stack of indices

Push -1 as a sentinel. Push each '(' index. On ')', pop. If stack becomes empty, push current i as the new base; otherwise the current valid length is i - stack.top().

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

function longestValidStack(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: Easiest to communicate. The -1 sentinel is the trick — it represents the base index just before the longest valid window starts.

3. DP with dp[i] = longest valid ending at i (optimal)

If s[i] === ')' and s[i-1] === '(', dp[i] = dp[i-2] + 2. If s[i-1] === ')' and s[i - dp[i-1] - 1] === '(', dp[i] = dp[i-1] + dp[i - dp[i-1] - 2] + 2.

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

function longestValidDP(s) {
  const n = s.length;
  const dp = new Array(n).fill(0);
  let best = 0;
  for (let i = 1; i < n; i++) {
    if (s[i] === ')') {
      if (s[i - 1] === '(') {
        dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
      } else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] === '(') {
        dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
      }
      best = Math.max(best, dp[i]);
    }
  }
  return best;
}

Tradeoff: Same O(n) time but more interview signal — you have to articulate the two recurrence cases. The trickier case is when s[i-1] is ')': skip backwards by dp[i-1] to find the matching open paren.

Netflix-specific tips

Netflix interviewers will accept either the stack solution or the DP solution. The stack is easier to write under pressure; the DP shows you understand the recurrence and is the version that scores higher. If you do the stack, be ready to explain WHY -1 is on the stack at the start. If you do the DP, narrate both recurrence cases before writing code.

Common mistakes

Forgetting the -1 sentinel on the stack — when the stack empties on ')' you can't compute the length without it.
In the DP, miscomputing `i - dp[i-1] - 2` — easy off-by-one source.
Returning the count of valid pairs instead of the longest contiguous substring length.

Follow-up questions

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

Could you do it in O(1) extra space? (Yes — two-pass counter approach scans left-to-right then right-to-left.)
What if the string had multiple types of brackets? (Becomes much harder — the dp recurrence breaks.)
Return the actual substring, not just the length.

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 is the stack solution often easier to communicate?

Because the invariant 'stack holds the base index just before the current valid window' is easy to state and easy to verify against examples. The DP version's two-case recurrence is correct but harder to talk through under interview pressure.

Is the two-counter O(1)-space solution worth learning?

Yes for follow-ups. Scan left-to-right tracking open and close counts; reset both when close > open; record length when they're equal. Scan right-to-left for the symmetric case. Total O(n) time, O(1) space.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →