## February LeetCoding Challenge 2021

Day 19

## Minimum Remove to Make Valid Parentheses

**PROBLEM STATEMENT:**

Given a string s of

Your task is to remove the minimum number of parentheses ( `'('`

, `')'`

and lowercase English characters.
`'('`

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`.`

## Explanation

This problem is similar to the problem of checking if the parenthesis is balanced or not. We are going to use the same approach however, instead of just telling if it is balanced or unbalanced we are going to remove the parentheses that makes it unbalanced.

**ALGORITHM: **

- Maintain a stack.
- Traverse the string from left to right.
- Push the
**index**of current character to the stack if it is ‘(‘. - If its an alphabet do nothing.
- If its a ‘)’ we first check if the stack is empty. If it is, that means that the current ‘)’ doesn’t have a corresponding ‘(‘. Replace that character with ‘*’ because it is making the parentheses unbalanced and thus need to be removed from final answer.
- If the stack is not empty pop the last element from the stack.
- Finally after traversing the string check if there is any element left in the stack.
- Replace the character present at the indices left in the stack with ‘*’ because it is again making the parentheses unbalanced and thus need to be removed from final answer 🙂

- Time complexity : O(n)
- Space complexity : O(n)

## code

## C++

```
class Solution {
public:
string minRemoveToMakeValid(string s) {
stack<int> st;
string res = "";
for(int i=0;i<s.length();++i){
if(s[i] == '('){
st.push(i);
}
else if(s[i] == ')'){
if(st.empty()){
s[i] = '*';
}
else st.pop();
}
}
while(!st.empty()){
s[st.top()] = '*';
st.pop();
}
for(char c : s){
if(c!='*') res += c;
}
return res;
}
};
```

## PYTHON

```
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
st = []
s = list(s)
for i in range(len(s)):
c = s[i]
if c == '(':
st.append(i)
elif c == ')':
if len(st)==0:
s[i] = '*'
else:
st.pop()
while len(st):
s[st[-1]] = '*'
st.pop()
res = ''
for c in s:
if c != '*':
res += c
return res
```