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:
AB (A concatenated with B), where A and B are valid strings, or(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^5s[i] is one of '(' , ')' and lowercase English letters.
The description was taken from https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/.
#O(N) Time, O(N) Spaceclass Solution: def minRemoveToMakeValid(self, s: str) -> str: s = list(s) opening = 0 for i in range(0, len(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)There are just two rules that we need to ensure are true to make the parentheses valid:
The parenthesis must be even.
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(0, len(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)