Minimum Remove to Make Valid Parentheses

Patrick Leaton
Problem 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.

 

The description was taken from https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/.

Problem Solution

#O(N) Time, O(N) Space
class Solution:
        def minRemoveToMakeValid(self, s: str) -> str:
            s = list(s)
            opening = 0
 
            for i in range(0len(s)):
                if s[i] == '(':
                    opening += 1
                elif s[i] == ')':
                    if opening == 0:
                        s[i] = ""
                    else:
                        opening -= 1
 
            for i in range(len(s)-1, -1, -1):
                if opening == 0:
                    break
                elif s[i] == '(':
                    s[i] = ""
                    opening -= 1
 
            return "".join(s)

Problem Explanation


There are just two rules that we need to ensure are true to make the parentheses valid:

  1. The parenthesis must be even.

  2. There can’t be closing parenthesis before opening ones.

 

With that being said, we will traverse the array left to right and remove any closing parentheses that are making the string invalid based on the second rule.

We can then traverse the array right to left and remove any opening parentheses that are making the string invalid based on the first rule.


Let's start off by converting the input string to an array since strings are immutable, and let's also initialize our opening parentheses counter.

            s = list(s)
            opening = 0

 

We will then make a loop for our first traversal.

            for i in range(0len(s)):

 

During each iteration, we will check if the element at our current index is an opening parenthesis.  If it is, then we will increment our opening parentheses counter.  

                if s[i] == '(':
                    opening += 1

 

If the current element in our iteration is a closing parenthesis, then we will want to check if we have had any opening parentheses yet due to our second rule.

If we haven't had any opening parentheses yet then this closing parenthesis is invalid, so we will remove it from our array.

                elif s[i] == ')':
                    if opening == 0:
                        s[i] = ""

 

Otherwise, if our current element is a closing parenthesis but we have a positive count of opening parentheses, we will decrement our opening parentheses counter to signify that we have matched two parentheses together.

                    else:
                        opening -= 1

 

After we have removed any closing parentheses that came before opening ones, we now need to traverse the array backward to remove any parentheses that are making the count uneven due to the first rule.

            for i in range(len(s)-1, -1, -1):

 

If we have a zero count of opening parentheses, then that means we have zero more opening parentheses than closing ones and we can break from our loop because we have an even count of opening and closing parentheses.

                if opening == 0:
                    break

 

If our opening parentheses counter is not zero, we will keep traversing the array to remove opening parentheses and to decrement our counter until the count of parentheses is even.

                elif s[i] == '(':
                    s[i] = ""
                    opening -= 1

 

Once all of the invalid parentheses have been removed, we will join the elements of our array together as a string and return it.

            return "".join(s)