32. Longest Valid Parentheses

Description

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses

substring

.

 

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

 

Constraints:

• 0 <= s.length <= 3 * 104
• s[i] is '(', or ')'.

 

Solutions

Solution: Stack

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
const longestValidParentheses = function (s) {
  const size = s.length;
  const stack = [];
  let result = (current = 0);

  for (let index = 0; index < size; index++) {
    current += 1;
    if (s[index] === '(') {
      stack.push(index);
      continue;
    }
    if (!stack.length) {
      current = 0;
      continue;
    }
    stack.pop();
    const length = stack.length ? index - stack.at(-1) : current;

    result = Math.max(length, result);
  }
  return result;
};