Skip to content

Latest commit

 

History

History
119 lines (90 loc) · 2.94 KB

032. Longest Valid Parentheses.md

File metadata and controls

119 lines (90 loc) · 2.94 KB
Raw
Difficulty Related Topics Similar Questions
Hard

32. Longest Valid Parentheses

Problem:

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

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

Solution:

ONE

DP.

Define f(i) to be the length of longest valid parentheses substring ended with s[i].

There are two types of valid parentheses substring:

  • lvps = type1 | type2 | [empty]
  • type1 = ( + lvps + )
  • type2 = lvps + lvps

Match type 1 and join type 2.

if s[i] == '(' // invalid string
  f(i) = 0
else if s[i - f(i-1) - 1] == '(' // match type1
  f(i) = (f(i-1) + 2) + f(i - f(i-1) - 2) // the length of type1 plus any type2 before it
else
  f(i) = 0
/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
  let dp = [0]
  for (let i = 1; i < s.length; i++) {
    dp[i] = s[i] === ')' && s[i - dp[i-1] - 1] === '('
      ? dp[i-1] + 2 + (dp[i - dp[i-1] - 2] || 0)
      : 0
  }
  return Math.max(...dp)
};

TWO

Inspired by 20. Valid Parentheses.

Take (() as example. When the last pair () matches, the first ( acts as the outer edge of the current longest valid parentheses substring whose length is 2 - 0 = 2.

Let the stack store the indices of the unmatched (s.

These indices are used to get the left outer edge of the current longest valid parentheses substring.

The bottom of the stack is specially used to store the initial left outer edge when there is no ( in the stack. The first of which is -1 of course. Later on it is the index of a ) when the stack is empty.

See comments in the code.

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
  const stack = [-1]
  let max = 0

  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      stack.push(i)
    } else {
      stack.pop() // This one is used to match the current ')'.
      if (stack.length > 0) {
        max =  Math.max(max, i - stack[stack.length - 1])
      } else {
        // Stack is empty,
        // which means the last popped item is not a '(' but the old special initial edge,
        // which also means the current `)` does no have a match.
        // Set the index of the current `)` as new initial edge.
        stack.push(i)
      }
    }
  }

  return max
};

Template generated via Leetmark.