Question

1249. 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.

 

Constraints:

• 1 <= s.length <= 105
• s[i] is either'(' , ')', or lowercase English letter.

Solutions

Solution 1: Two Passes

First, we scan from left to right and remove the extra right parentheses. Then, we scan from right to left and remove the extra left parentheses.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the string $s$.

Similar problems:

• 678. Valid Parenthesis String
• 2116. Check if a Parentheses String Can Be Valid

class Solution:
  def minRemoveToMakeValid(self, s: str) -> str:
    stk = []
    x = 0
    for c in s:
      if c == ')' and x == 0:
        continue
      if c == '(':
        x += 1
      elif c == ')':
        x -= 1
      stk.append(c)
    x = 0
    ans = []
    for c in stk[::-1]:
      if c == '(' and x == 0:
        continue
      if c == ')':
        x += 1
      elif c == '(':
        x -= 1
      ans.append(c)
    return ''.join(ans[::-1])

class Solution {
  public String minRemoveToMakeValid(String s) {
    Deque<Character> stk = new ArrayDeque<>();
    int x = 0;
    for (int i = 0; i < s.length(); ++i) {
      char c = s.charAt(i);
      if (c == ')' && x == 0) {
        continue;
      }
      if (c == '(') {
        ++x;
      } else if (c == ')') {
        --x;
      }
      stk.push(c);
    }
    StringBuilder ans = new StringBuilder();
    x = 0;
    while (!stk.isEmpty()) {
      char c = stk.pop();
      if (c == '(' && x == 0) {
        continue;
      }
      if (c == ')') {
        ++x;
      } else if (c == '(') {
        --x;
      }
      ans.append(c);
    }
    return ans.reverse().toString();
  }
}

class Solution {
public:
  string minRemoveToMakeValid(string s) {
    string stk;
    int x = 0;
    for (char& c : s) {
      if (c == ')' && x == 0) continue;
      if (c == '(')
        ++x;
      else if (c == ')')
        --x;
      stk.push_back(c);
    }
    string ans;
    x = 0;
    while (stk.size()) {
      char c = stk.back();
      stk.pop_back();
      if (c == '(' && x == 0) continue;
      if (c == ')')
        ++x;
      else if (c == '(')
        --x;
      ans.push_back(c);
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
};

func minRemoveToMakeValid(s string) string {
  stk := []byte{}
  x := 0
  for i := range s {
    c := s[i]
    if c == ')' && x == 0 {
      continue
    }
    if c == '(' {
      x++
    } else if c == ')' {
      x--
    }
    stk = append(stk, c)
  }
  ans := []byte{}
  x = 0
  for i := len(stk) - 1; i >= 0; i-- {
    c := stk[i]
    if c == '(' && x == 0 {
      continue
    }
    if c == ')' {
      x++
    } else if c == '(' {
      x--
    }
    ans = append(ans, c)
  }
  for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
    ans[i], ans[j] = ans[j], ans[i]
  }
  return string(ans)
}

function minRemoveToMakeValid(s: string): string {
  let left = 0;
  let right = 0;
  for (const c of s) {
    if (c === '(') {
      left++;
    } else if (c === ')') {
      if (right < left) {
        right++;
      }
    }
  }

  let hasLeft = 0;
  let res = '';
  for (const c of s) {
    if (c === '(') {
      if (hasLeft < right) {
        hasLeft++;
        res += c;
      }
    } else if (c === ')') {
      if (hasLeft != 0 && right !== 0) {
        right--;
        hasLeft--;
        res += c;
      }
    } else {
      res += c;
    }
  }
  return res;
}

impl Solution {
  pub fn min_remove_to_make_valid(s: String) -> String {
    let bs = s.as_bytes();
    let mut right = {
      let mut left = 0;
      let mut right = 0;
      for c in bs.iter() {
        match c {
          &b'(' => {
            left += 1;
          }
          &b')' if right < left => {
            right += 1;
          }
          _ => {}
        }
      }
      right
    };
    let mut has_left = 0;
    let mut res = vec![];
    for c in bs.iter() {
      match c {
        &b'(' => {
          if has_left < right {
            has_left += 1;
            res.push(*c);
          }
        }
        &b')' => {
          if has_left != 0 && right != 0 {
            right -= 1;
            has_left -= 1;
            res.push(*c);
          }
        }
        _ => {
          res.push(*c);
        }
      }
    }
    String::from_utf8_lossy(&res).to_string()
  }
}