Minimum remove to make valid parentheses (Leetcode 1249)
Remove duplicates in place (Leetcode 26)
Bias-variance equation
Remove duplicates in place (Leetcode 26)
Bias-variance equation
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:
- If the stack is empty, then this means that you will need to remove this right parenthesis from the input string. So you add its index in a set to remove at the end.
- If the stack is not empty, then you pop out an element from the stack.
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)\).
Stack
- Remove duplicates in place (Leetcode 26) Easy (Array, Two pointers)
- Longest substring without repeating characters (Leetcode 3) Medium (Hash, Sliding Window)
- K Closest Points to Origin (Leetcode 973) Easy (Heap)
- Number of recent calls (Leetcode 933) Easy (Queue, DEQueue)
- Climbing stairs (Leetcode 70) Easy (Recursion, Dynamic programming)
Thank you, we have received your feedback.