# 301. Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses `(` and `)`.

Example 1:

``````Input: "()())()"
Output: ["()()()", "(())()"]
``````

Example 2:

``````Input: "(a)())()"
Output: ["(a)()()", "(a())()"]
``````

Example 3:

``````Input: ")("
Output: [""]
``````

Credits:
Special thanks to @hpplayer for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

``````class Solution {
public:
vector<string> removeInvalidParentheses(string s) {
vector<string> res;
unordered_set<string> visited{{s}};
queue<string> q{{s}};
bool found = false;
while (!q.empty()) {
string t = q.front(); q.pop();
if (isValid(t)) {
res.push_back(t);
found = true;
}
if (found) continue;
for (int i = 0; i < t.size(); ++i) {
if (t[i] != '(' && t[i] != ')') continue;
string str = t.substr(0, i) + t.substr(i + 1);
if (!visited.count(str)) {
q.push(str);
visited.insert(str);
}
}
}
return res;
}
bool isValid(string t) {
int cnt = 0;
for (int i = 0; i < t.size(); ++i) {
if (t[i] == '(') ++cnt;
else if (t[i] == ')' && --cnt < 0) return false;
}
return cnt == 0;
}
};
``````

``````class Solution {
public:
vector<string> removeInvalidParentheses(string s) {
vector<string> res;
int cnt1 = 0, cnt2 = 0;
for (char c : s) {
cnt1 += (c == '(');
if (cnt1 == 0) cnt2 += (c == ')');
else cnt1 -= (c == ')');
}
helper(s, 0, cnt1, cnt2, res);
return res;
}
void helper(string s, int start, int cnt1, int cnt2, vector<string>& res) {
if (cnt1 == 0 && cnt2 == 0) {
if (isValid(s)) res.push_back(s);
return;
}
for (int i = start; i < s.size(); ++i) {
if (i != start && s[i] == s[i - 1]) continue;
if (cnt1 > 0 && s[i] == '(') {
helper(s.substr(0, i) + s.substr(i + 1), i, cnt1 - 1, cnt2, res);
}
if (cnt2 > 0 && s[i] == ')') {
helper(s.substr(0, i) + s.substr(i + 1), i, cnt1, cnt2 - 1, res);
}
}
}
bool isValid(string t) {
int cnt = 0;
for (int i = 0; i < t.size(); ++i) {
if (t[i] == '(') ++cnt;
else if (t[i] == ')' && --cnt < 0) return false;
}
return cnt == 0;
}
};
``````

``````class Solution {
public:
vector<string> removeInvalidParentheses(string s) {
vector<string> res;
helper(s, 0, 0, {'(', ')'}, res);
return res;
}
void helper(string s, int last_i, int last_j, vector<char> p, vector<string>& res) {
int cnt = 0;
for (int i = last_i; i < s.size(); ++i) {
if (s[i] == p[0]) ++cnt;
else if (s[i] == p[1]) --cnt;
if (cnt >= 0) continue;
for (int j = last_j; j <= i; ++j) {
if (s[j] == p[1] && (j == last_j || s[j] != s[j - 1])) {
helper(s.substr(0, j) + s.substr(j + 1), i, j, p, res);
}
}
return;
}
string rev = string(s.rbegin(), s.rend());
if (p[0] == '(') helper(rev, 0, 0, {')', '('}, res);
else res.push_back(rev);
}
};
``````

``````class Solution {
public:
vector<string> removeInvalidParentheses(string s) {
vector<string> res;
unordered_set<string> cur{{s}};
while (!cur.empty()) {
unordered_set<string> next;
for (auto &a : cur) {
if (isValid(a)) res.push_back(a);
if (!res.empty()) continue;
for (int i = 0; i < a.size(); ++i) {
if (a[i] != '(' && a[i] != ')') continue;
next.insert(a.substr(0, i) + a.substr(i + 1));
}
}
if (!res.empty()) return res;
cur = next;
}
return res;
}
bool isValid(string t) {
int cnt = 0;
for (int i = 0; i < t.size(); ++i) {
if (t[i] == '(') ++cnt;
else if (t[i] == ')' && --cnt < 0) return false;
}
return cnt == 0;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/301

Longest Valid Parentheses

Generate Parentheses

Valid Parentheses

https://leetcode.com/problems/remove-invalid-parentheses/

https://leetcode.com/problems/remove-invalid-parentheses/discuss/75032/share-my-java-bfs-solution

https://leetcode.com/problems/remove-invalid-parentheses/discuss/75027/easy-short-concise-and-fast-java-dfs-3-ms-solution

https://leetcode.com/problems/remove-invalid-parentheses/discuss/75046/c-depth-limited-dfs-3ms-eliminate-duplicates-without-hashmap

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation