Skip to main content

86. Longest Valid Parentheses

hardAsked at Salesforce

Find the longest valid (well-formed) parentheses substring. Salesforce uses this as a stack/DP hybrid that tests both approaches.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses balanced-paren tracking in their SOQL query validation.
  • Blind (2025)— Salesforce hard onsite question.

Problem

Given a string containing just the characters '(' and ')', find 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: The longest valid parentheses substring is "()".

Example 2

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

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

Example 3

Input
s = ""
Output
0

Approaches

1. Brute force all substrings

Check every substring with a stack.

Time
O(n^3)
Space
O(n)
// Cubic. Not acceptable.

Tradeoff: TLE.

2. Stack with sentinel index

Stack holds indices of unmatched parens. Push -1 sentinel. On '(', push i. On ')', pop; if stack empty, push i as new sentinel; else update best = 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) stack.push(i);
      else best = Math.max(best, i - stack[stack.length - 1]);
    }
  }
  return best;
}

Tradeoff: Single pass. The -1 sentinel anchors the leftmost 'invalid' boundary. After every match, i - stack.top gives the current valid length.

Salesforce-specific tips

Salesforce uses balanced-paren tracking in their SOQL query validation (counting and tracking unmatched parens to give helpful error messages). They grade on whether you spot the sentinel trick. Bonus signal: also discuss the O(1) space two-pass solution that uses just two counters (open and close).

Common mistakes

  • Not pushing -1 initially — boundary calculation is off.
  • Pushing every char onto stack instead of just unmatched indices.
  • Confusing 'count of matched' with 'length of substring' — they're equal but the formulation differs.

Follow-up questions

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

  • Generate Parentheses (LC 22).
  • Valid Parentheses (LC 20).
  • Maximum nested depth of parentheses.

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 anchors the 'before the start' position. After matching, i - stack.top gives the valid length up through i.

Is there an O(1) space solution?

Yes — two-pass with open/close counters. Pass left-to-right; reset when close > open. Pass right-to-left mirror-image. Track max over both.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →