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(Aconcatenated withB), whereAandBare valid strings, or - It can be written as
(A), whereAis 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 <= 105s[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) == '(') {
stack.add(i);
} else if (s.charAt(i) == ')') {
if (!stack.isEmpty()) {
validIndexes.add(stack.pop());
validIndexes.add(i);
}
}
}
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();
}
}
Input
Output
#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('')
};
Input
Output
#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
Input
Output
#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;
}
}
}
Input
Output