You can access a significantly larger sample of the platform's content for free by logging in with your Gmail account. Sign in now to explore.

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.

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`

To solve this problem we can use a stack. The general idea is that you add the positions of left parentheses in the stack. If you come across a right

`)`

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 inpiutmaps 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

- Sample from random generator Medium (Sample, Uniform, Random number generator)
- Gambler’s ruin win probability Medium (Gambler ruin, Random walk, Expectation)
- Remove duplicates in place (leetcode 26) Easy (Array, Two pointers)
- Prussian horses Medium (Poisson, Hypothesis testing, CDF)
- Principal Component Analysis (PCA) from scratch Medium (Principal Component Analysis (PCA))