Algorithm
Problem Name: 301. Remove Invalid Parentheses
Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.
Return a list of unique strings that are valid with the minimum number of removals. You may return the answer in any order.
Example 1:
Input: s = "()())()" Output: ["(())()","()()()"]
Example 2:
Input: s = "(a)())()" Output: ["(a())()","(a)()()"]
Example 3:
Input: s = ")("
Output: [""]
Constraints:
1 <= s.length <= 25sconsists of lowercase English letters and parentheses'('and')'.- There will be at most
20parentheses ins.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct {
char **p;
int psz, pn;
} res_t;
char *substr(char *s, int l, int i) {
char *buff = malloc(l * sizeof(char));
//assert(buff);
strncpy(buff, s, i - 0);
strcpy(&buff[i - 0], &s[i + 1]);
return buff;
}
void reverse(char *buff, int l) {
int i, j;
char x;
for (i = 0, j = l - 1; i < j; i ++, j --) {
x = buff[i];
buff[i] = buff[j];
buff[j] = x;
}
}
void add_result(res_t *res, char *s) {
if (res->psz == 0) {
res->psz = 10;
res->p = malloc(res->psz * sizeof(char *));
//assert(res->p);
} else if (res->psz == res->pn) {
res->psz *= 2;
res->p = realloc(res->p, res->psz * sizeof(char *));
//assert(res->p);
}
res->p[res->pn ++] = s;
}
void remove1(char *s, int l, int si, int sj, res_t *res, char c1, char c2) {
int i, j, d = 0;
char *buff;
for (j = sj; j < l; j ++) {
if (s[j] == c1) d ++;
else if (s[j] == c2) d --;
if (d < 0) {
// found one invalid parenthese
for (i = si; i <= j; i ++) {
if (s[i] == c2 && (i == si || s[i - 1] != c2)) {
// make a new stirng by removing this invalid parenthese
buff = substr(s, l, i);
remove1(buff, l - 1, i, j, res, c1, c2);
}
}
free(s); // free the invalid string
return;
}
}
reverse(s, l);
if (c1 == '(') {
remove1(s, l, 0, 0, res, c2, c1);
return;
}
// done, s is a valid one
add_result(res, s);
}
char** removeInvalidParentheses(char* s, int* returnSize) {
res_t res = { 0 };
char *buff;
int l;
l = strlen(s);
buff = malloc((l + 1) * sizeof(char));
//assert(buff);
strcpy(buff, s);
remove1(buff, l, 0, 0, &res, '(', ')');
*returnSize = res.pn;
return res.p;
}
Input
s = "()())()"
Output
["(())()","()()()"]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<string> removeInvalidParentheses(string s) {
vector<string>res;
int minMove = INT_MAX;
backtrack(res, s, 0, 0, minMove);
return res;
}
void backtrack(vector < string>& res, string s, int pos, int move, int& minMove){
if(pos > s.size() || move > minMove) return;
if(isValid(s)){
if(move < minMove) res.clear(), res.push_back(s), minMove = move;
else if(move == minMove && find(res.begin(), res.end(), s) == res.end()) res.push_back(s);
return;
}
while(pos < s.size() && s[pos] != '(' && s[pos] != ')'> pos++;
if(pos >= s.size()) return;
backtrack(res, s.substr(0, pos) + s.substr(pos + 1), pos, move + 1, minMove);
backtrack(res, s, pos + 1, move, minMove);
}
bool isValid(string& s){
int sum = 0;
for(auto c: s){
if(c == '(') sum++;
else if(c == ')') sum--;
if(sum < 0> return false;
}
return sum == 0;
}
};
Input
s = "()())()"
Output
["(())()","()()()"]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
Set validStrings;
int minimumRemoved;
public List < String> removeInvalidParentheses(String s) {
validStrings = new HashSet<>();
minimumRemoved = Integer.MAX_VALUE;
backtrack(s, 0, 0, 0, new StringBuilder(), 0);
return new ArrayList < >(validStrings);
}
private void backtrack(String s, int idx, int leftCount, int rightCount, StringBuilder sb, int removedCount) {
if (idx == s.length()) {
if (leftCount == rightCount) {
if (removedCount <= minimumRemoved) {
String possibleAns = sb.toString();
if (removedCount < minimumRemoved) {
validStrings.clear();
minimumRemoved = removedCount;
}
validStrings.add(possibleAns);
}
}
}
else {
char c = s.charAt(idx);
if (c != '(' && c != ')') {
sb.append(c);
backtrack(s, idx + 1, leftCount, rightCount, sb, removedCount);
sb.deleteCharAt(sb.length() - 1);
}
else {
backtrack(s, idx + 1, leftCount, rightCount, sb, removedCount + 1);
sb.append(c);
if (c == '(') {
backtrack(s, idx + 1, leftCount + 1, rightCount, sb, removedCount);
}
else if (rightCount < leftCount) {
backtrack(s, idx + 1, leftCount, rightCount + 1, sb, removedCount);
}
sb.deleteCharAt(sb.length() - 1);
}
}
}
}
Input
s = "(a)())()"
Output
["(a())()","(a)()()"]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const removeInvalidParentheses = function(s) {
const res = []
helper(s, 0, 0, ['(', ')'])
return res
function helper(str, lastI, lastJ, pair) {
let openNum = 0, closeNum = 0
for(let i = lastI; i < str.length; i++) {
if(str[i] === pair[0]) openNum++
if(str[i] === pair[1]) closeNum++
if(closeNum > openNum) {
for(let j = lastJ; j <= i; j++) {
if(str[j] === pair[1] && (j === lastJ || str[j - 1] !== pair[1])) {
helper(str.slice(0, j) + str.slice(j + 1), i, j, pair)
}
}
return
}
}
let rev = str.split('').reverse().join('')
if(pair[0] === '(') {
helper(rev, 0, 0, [')', '('])
} else {
res.push(rev>
}
}
};
Input
s = "(a)())()"
Output
["(a())()","(a)()()"]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def removeInvalidParentheses(self, s):
l = r = 0
for c in s:
if c.isalpha(): continue
if c == "(": l += 1
elif l: l -= 1
else: r += 1
q = {("", l, r, 0, 0)}
for c in s:
new = set()
for st, l, r, lCur, rCur in q:
if c == "(":
new.add((st + c, l, r, lCur + 1, rCur))
if l:
new.add((st, l - 1, r, lCur, rCur))
elif c == ")":
if lCur:
new.add((st + c, l, r, lCur - 1, rCur))
else:
new.add((st + c, l, r, lCur, rCur + 1))
if r:
new.add((st, l, r - 1, lCur, rCur))
else:
new.add((st + c, l, r, lCur, rCur))
q = new
return list({st for st, l, r, lCur, rCur in q if l == r == lCur == rCur == 0})
Input
s = ")("
Output
[""]
#6 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
using System.Text;
namespace LeetCode
{
public class _0301_RemoveInvalidParentheses
{
public IList < string> RemoveInvalidParentheses(string s)
{
int invalidLeft = 0, invalidRight = 0;
foreach (var ch in s)
{
if (ch == '(') invalidLeft++;
else if (ch == ')')
{
invalidRight = invalidLeft == 0 ? invalidRight + 1 : invalidRight;
invalidLeft = invalidLeft == 0 ? invalidLeft : invalidLeft - 1;
}
}
var result = new HashSet < string>();
RemoveInvalidParentheses(s, 0, 0, 0, invalidLeft, invalidRight, new StringBuilder(), result);
return new List < string>(result);
}
private void RemoveInvalidParentheses(string s, int index, int leftCount, int rightCount, int invalidLeft, int invalidRight, StringBuilder sb, HashSet result)
{
if (s.Length == index)
{
if (invalidLeft == 0 && invalidRight == 0) result.Add(sb.ToString());
return;
}
var ch = s[index];
if ((ch == '(' && invalidLeft > 0) || (ch == ')' && invalidRight > 0))
RemoveInvalidParentheses(s, index + 1, leftCount, rightCount, invalidLeft - (ch == '(' ? 1 : 0), invalidRight - (ch == ')' ? 1 : 0), sb, result);
sb.Append(ch);
if (ch != '(' && ch != ')')
RemoveInvalidParentheses(s, index + 1, leftCount, rightCount, invalidLeft, invalidRight, sb, result);
else if (ch == '(')
RemoveInvalidParentheses(s, index + 1, leftCount + 1, rightCount, invalidLeft, invalidRight, sb, result);
else if (rightCount < leftCount)
RemoveInvalidParentheses(s, index + 1, leftCount, rightCount + 1, invalidLeft, invalidRight, sb, result);
sb.Remove(sb.Length - 1, 1);
}
}
}
Input
s = ")("
Output
[""]