Longest valid parentheses

Hard TimeO(n) SpaceO(n)

Given a string of only ( and ), return the length of the longest contiguous stretch that is well formed — every opener inside it closed inside it. A string with no valid stretch answers 0.

Examples

Example 1

Input
s = ")()())"
Output
4
()() in the middle is four long; the brackets at either end never find a partner.

Example 2

Input
s = "((("
Output
0
Three openers and no closers, so not one stretch is well formed.

The Code

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 {
        const length = i - stack[stack.length - 1];
        if (length > best) best = length;
      }
    }
  }
  return best;
}
longestValidParentheses(")()())");
Done
Step through longestValidParentheses(")()())") call by call

More like this

All dynamic programming examples (20) →