1249. Minimum Remove to Make Valid Parentheses

Problem Statement

link: LeetCode.cn LeetCode

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:

Input: s = "lee(t(c)o)de)" Output: "lee(t(c)o)de"

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

Input: s = "))((" Output: ""

Constraints:

1 <= s.length <= 10^5 s[i] is either ‘(‘ , ‘)’, or lowercase English letter.

Solution Approach

The algorithm uses a stack-based approach to balance parentheses by first ensuring that all open parentheses have a matching closing parenthesis, and then removing any extra open parentheses left unmatche

Algorithm

1. Stack-Based Processing: The solution uses a stack-like approach to ensure that every closing parenthesis ) has a matching opening parenthesis ( by keeping track of unmatched parentheses and adding characters to a result list accordingly.
2. Two-Pass Approach: The algorithm performs two passes through the string: the first pass builds the intermediate result while balancing parentheses, and the second pass removes any unmatched opening parentheses from the end of the result list.
3. Efficient Handling: By iterating through the string only twice and using a single list for results, the solution achieves a time complexity of O(N) and a space complexity of O(N), making it efficient for large input sizes.

   Complexity

   time complexity: O(n) space complexity: O(n)

Implement

    class Solution:
  def validParentheses(self, s:str) -> str:
      removeIdx = []
      stack = []
      for i in range(len(s)):# 7  i = 6  removeIdx=[1] stack=[]
          if s[i] == '(':
              stack.append(i)
          if s[i] == ')':
              if stack:
                  stack.pop()
              else:
                  removeIdx.append(i)
      if stack:
          removeIdx = removeIdx + stack
      removeIdx = set(removeIdx) #removeIdx = {1}
      res = ''
      for i in range(len(s)): # "a  b ( c ) d"
          if i not in removeIdx:
              res += s[i]
      return res


class Solution:
  def minRemoveToMakeValid(self, s: str) -> str:
      ct = 0
      res = []
      for c in s:
          if c == '(':
              ct += 1
              res.append(c)
          elif c == ')':
              if ct > 0:
                  ct -= 1
                  res.append(c)
          else:
              res.append(c)
      for i in range(len(res) - 1, -1, -1):
          if ct == 0:
              break
          if res[i] == "(":
              ct -= 1
              res[i] = ""
      return ''.join(res)

 

    
    

Twitter  facebook  Email