Skip to content

32. Longest Valid Parentheses

https://leetcode.com/problems/longest-valid-parentheses/

js
/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
  var result = 0
  var stack = []

  for (let i = 0; i < s.length; i++) {
    let ch = s[i]
    if (ch === ')' && stack.length && s[stack[stack.length - 1]] === '(') {
      stack.pop()
      if (stack.length) {
        result = Math.max(result, i - stack[stack.length - 1])
      } else {
        result = i + 1
      }
    } else {
      stack.push(i)
    }
  }

  return result
}
py
class Solution(object):

    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        result, stack = 0, []
        for i, c in enumerate(s):
            if c == ')' and len(stack) > 0 and s[stack[-1]] == '(':
                stack.pop()
                if len(stack) > 0:
                    result = max(result, i - stack[-1])
                else:
                    result = i + 1
            else:
                stack.append(i)
        return result