## Algorithm

Problem Name: 1249. Minimum Remove to Make Valid Parentheses

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.

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

Constraints:

• `1 <= s.length <= 105`
• `s[i]` is either`'('` , `')'`, or lowercase English letter`.`

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public String minRemoveToMakeValid(String s) {
Stack stack = new Stack<>();
Set < Integer> validIndexes = new HashSet<>();
for (int i = 0; i  <  s.length(); i++) {
if (s.charAt(i) == '(') {
} else if (s.charAt(i) == ')') {
if (!stack.isEmpty()) {
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i  <  s.length(); i++) {
if (s.charAt(i) == '(' || s.charAt(i) == ')') {
if (validIndexes.contains(i)) {
sb.append(s.charAt(i));
}
} else {
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}
``````
Copy The Code &

Input

cmd
s = "lee(t(c)o)de)"

Output

cmd
"lee(t(c)o)de"

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const minRemoveToMakeValid = function(s) {
const stack = [], n = s.length
const arr = s.split('')
let res = ''
for(let i = 0; i  <  n; i++) {
if(s[i] === '(') stack.push(i + 1)
if(s[i] === ')') {
if(stack.length && stack[stack.length - 1] >= 0) stack.pop()
else stack.push(-(i + 1))
}
}
while(stack.length) {
arr[Math.abs(stack.pop()) - 1] = ''
}
return arr.join('')
};
``````
Copy The Code &

Input

cmd
s = "lee(t(c)o)de)"

Output

cmd
"lee(t(c)o)de"

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def minRemoveToMakeValid(
self, s: str, res: str = "", l: str = "(", r: str = ")", b: int = 0
) -> str:
for _ in range(2):
for c in s:
if c == r and b <= 0:
continue
b += c == l
b -= c == r
res += c
res, s, l, r, b = "", res[::-1], r, l, 0
return s
``````
Copy The Code &

Input

cmd
s = "a)b(c)d"

Output

cmd
"ab(c)d"

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Linq;
using System.Text;

namespace LeetCode
{
public class _1249_MinimumRemoveToMakeValidParentheses
{
public string MinRemoveToMakeValid(string s)
{
var sb = RemoveInvalidClosing(s.ToArray(), '(', ')');
sb = RemoveInvalidClosing(sb.ToString().Reverse().ToArray(), ')', '(');
return new string(sb.ToString().Reverse().ToArray());
}

private StringBuilder RemoveInvalidClosing(char[] s, char open, char close)
{
var sb = new StringBuilder();
int balance = 0;

foreach (var ch in s)
{
if (ch == open) balance++;
if (ch == close)
{
if (balance == 0) continue;
balance--;
}
sb.Append(ch);
}
return sb;
}
}
}
``````
Copy The Code &

Input

cmd
s = "a)b(c)d"

Output

cmd
"ab(c)d"