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.
Leetcode 1249: https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/description/
Examples:
Input: s = m(a(d))), Output:m(a(d))
Input: s = "a)b(c)d", Output: ab(c)d
) parenthesis then:
At the end, you will come across two scenarios: - The stack is empty, in which case you are good to go by removing only the early right parentheses indexes you have already saved. - Or, the stack is non-empty, which means that there are a bunch of additional left parentheses unmatched. In that case, you remove the indexes remaining in the stack as well.
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
stack = []
indexes_to_remove = set()
for i,l in enumerate(s):
if l in "()":
if not stack and l == ")":
indexes_to_remove.add(i)
elif l == "(":
stack.append(i)
else:
stack.pop()
# add the remaining of the stack
indexes_to_remove = indexes_to_remove.union(set(stack))
return "".join([l for i,l in enumerate(s) if i not in indexes_to_remove])
If we wanted to run it on an example:
## 'm(a(d))'
The time complexity of this solution is \(O(N)\), since there is no nested for loop. Note that despite the fact that go over N twice, this is still \(O(N)\) as \(O(cN)\), where \(c\) is a constant and not an inpiut maps to \(O(N)\). The space complexity is again O(N): up to \(N\) elements in the stack, up to \(N\) elements in the set, hence the result is \(O(N)\).