Skip to main content

86. Longest Valid Parentheses

hardAsked at Plaid

Find the length of the longest valid parentheses substring. Plaid asks this as a stack-based scanning problem — the same shape they use to find the longest run of properly-paired JSON braces in a corrupted webhook payload.

By Sam K., Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE III hard string.
  • LeetCode Discuss (2026)— Plaid stack-based 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

Example 2

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

Example 3

Input
s = ""
Output
0

Approaches

1. Try every substring

Check every (i, j) for validity; track longest.

Time
O(n^3)
Space
O(n)
// Cubic. Don't ship.

Tradeoff: TLE.

2. Stack of indices

Push -1 as a sentinel. Push '(' index. On ')', pop. If stack empty, push current index as new sentinel; else compute 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. The sentinel -1 (and re-seed on empty pop) is the trick that lets you compute the length as i - stack.top in all cases.

Plaid-specific tips

Plaid grades this on whether the sentinel trick comes naturally. Bonus signal: derive why the sentinel encodes 'the last invalid position.' Connect to webhook-payload repair where finding the longest balanced run is the prefix to the corruption point.

Common mistakes

  • Forgetting the initial -1 sentinel.
  • Not re-seeding the sentinel when the stack becomes empty.
  • Storing characters instead of indices on the stack.

Follow-up questions

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

  • Return the substring itself.
  • Return all maximal valid substrings.
  • DP variant — equivalent asymptotic.

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 as the initial sentinel?

It encodes 'the position just before the string,' so when we compute length = i - sentinel, we get the correct length for matches starting at index 0.

Why re-seed on empty pop?

An unmatched ')' invalidates everything before it. We push its index as the new sentinel so subsequent matches measure from there.

More Plaid coding interview questions

See all Plaid problems →

Companies that also ask Longest Valid Parentheses