JS pen questions – the longest valid parentheses subset

Topic:

Given a string containing only ‘(‘ and ‘)’, find the length of the longest valid (well-formed and continuous) parenthesis substring.

Example 1:

Input: s = “(()” Output: 2 Explanation: The longest valid parenthesis substring is “()”

Example 2:

Input: s = “)()())” Output: 4 Explanation: The longest valid parenthesis substring is “()()”

Example 3:

Input: s = “output: 0

Analysis:

• A string is valid only if the number of open parentheses equals the number of close parentheses, and the open parentheses precede the close parentheses.
• There are no other characters involved, so it’s relatively easy. You can count the left and right parentheses separately and determine the current difference between the two.
• Traversal from left to right, once the number of close parentheses is more than the number of open parentheses, it means that the close parentheses appear before the open parentheses; On the other hand, when traversing from right to left, once there are more open parentheses than close parentheses, it means that the open parentheses appear after the close parentheses.

Complete code:

/ * * *@param {string} s
 * @return {number}* /
var longestValidParentheses = function(s) {
  let maxLength = 0;
  let left = 0, right = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      left++;
    } else {
      right++;
    }

    if (left - right < 0) {
      left = right = 0;
    } else if (left === right) {
      maxLength = Math.max(maxLength, left + right);
    }
  }

  left = right = 0;
  for (let i = s.length - 1; i >= 0; i--) {
    if (s[i] === '(') {
      left++;
    } else {
      right++;
    }

    if (left - right > 0) {
      left = right = 0;
    } else if (left === right) {
      maxLength = Math.max(maxLength, left + right); }}return maxLength;
};
Copy the code