Minimum Remove to Make Valid Parentheses

Description

Given a string s of '(' , ')' and lowercase English characters. 

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

• It is the empty string, contains only lowercase characters, or
• It can be written as AB (A concatenated with B), where A and B are valid strings, or
• It can be written as (A), where A is a valid string.

 

Example 1:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2:

Input: s = "a)b(c)d"
Output: "ab(c)d"

Example 3:

Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.

Example 4:

Input: s = "(a(b(c)d)"
Output: "a(b(c)d)"

 

Constraints:

• 1 <= s.length <= 10^5
• s[i] is one of  '(' , ')' and lowercase English letters.

Solution(javascript)

/* eslint-disable no-lonely-if */
/*
 * @lc app=leetcode id=1249 lang=javascript
 *
 * [1249] Minimum Remove to Make Valid Parentheses
 */

// @lc code=start
/**
 * @param {string} s
 * @return {string}
 */
const minRemoveToMakeValid = function (s) {
  const stack = []
  const isLeftP = x => x === '('
  const isRightP = x => x === ')'
  const isP = x => (isLeftP(x) || isRightP(x))
  for (const c of s) {
    if (stack.length === 0) {
      stack.push(c)
      continue
    }

    if (isRightP(c)) {
      let current = ''
      if (isLeftP(stack[stack.length - 1])) { // NOTE 这里先校验倒数第一个是括号的情况
        current = stack.pop() + c
      } else if (isLeftP(stack[stack.length - 2])) {
        const value = stack.pop()
        const leftP = stack.pop()
        current = (leftP + value + c)
      }
      if (stack[stack.length - 1] && !isP(stack[stack.length - 1])) {
        current = stack.pop() + current
      }
      stack.push(current)
    } else if (isLeftP(c)) {
      stack.push('(')
    } else {
      if (!isP(stack[stack.length - 1])) {
        stack[stack.length - 1] += c
      } else {
        stack.push(c)
      }
    }
  }
  // console.log(stack)
  return stack.filter(x => !isP(x)).join('')
}
// @lc code=end