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 all the possible results. 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 <= 25
s
consists of lowercase English letters and parentheses'('
and')'
.- There will be at most
20
parentheses ins
.
Remove Invalid Parentheses Solutions
✅Time: O(n)
✅Space: O(n+∣ans∣)
C++
class Solution {
public:
vector<string> removeInvalidParentheses(string s) {
vector<string> ans;
const auto [l, r] = getLeftAndRightCounts(s);
dfs(s, 0, l, r, ans);
return ans;
}
private:
// very similar to 921. Minimum Add to Make Parentheses Valid
// return how many '(' and ')' need to be deleted
pair<int, int> getLeftAndRightCounts(const string& s) {
int l = 0;
int r = 0;
for (const char c : s)
if (c == '(')
++l;
else if (c == ')') {
if (l == 0)
++r;
else
--l;
}
return {l, r};
}
void dfs(const string& s, int start, int l, int r, vector<string>& ans) {
if (l == 0 && r == 0 && isValid(s)) {
ans.push_back(s);
return;
}
for (int i = start; i < s.length(); ++i) {
if (i > start && s[i] == s[i - 1])
continue;
if (l > 0 && s[i] == '(') // delete s[i]
dfs(s.substr(0, i) + s.substr(i + 1), i, l - 1, r, ans);
if (r > 0 && s[i] == ')') // delete s[i]
dfs(s.substr(0, i) + s.substr(i + 1), i, l, r - 1, ans);
}
}
bool isValid(const string& s) {
int count = 0; // # of '(' - # of ')'
for (const char c : s) {
if (c == '(')
++count;
else if (c == ')')
--count;
if (count < 0)
return false;
}
return true; // count == 0
}
};
Java
class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> ans = new ArrayList<>();
final int[] counts = getLeftAndRightCounts(s);
dfs(s, 0, counts[0], counts[1], ans);
return ans;
}
// very similar to 921. Minimum Add to Make Parentheses Valid
// return how many '(' and ')' need to be deleted
private int[] getLeftAndRightCounts(final String s) {
int l = 0;
int r = 0;
for (final char c : s.toCharArray())
if (c == '(')
++l;
else if (c == ')') {
if (l == 0)
++r;
else
--l;
}
return new int[] {l, r};
}
private void dfs(final String s, int start, int l, int r, List<String> ans) {
if (l == 0 && r == 0 && isValid(s)) {
ans.add(s);
return;
}
for (int i = start; i < s.length(); ++i) {
if (i > start && s.charAt(i) == s.charAt(i - 1))
continue;
if (l > 0 && s.charAt(i) == '(') // delete s[i]
dfs(s.substring(0, i) + s.substring(i + 1), i, l - 1, r, ans);
else if (r > 0 && s.charAt(i) == ')') // delete s[i]
dfs(s.substring(0, i) + s.substring(i + 1), i, l, r - 1, ans);
}
}
private boolean isValid(final String s) {
int count = 0; // # of '(' - # of ')'
for (final char c : s.toCharArray()) {
if (c == '(')
++count;
else if (c == ')')
--count;
if (count < 0)
return false;
}
return true; // count == 0
}
}
Python
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
def getLeftAndRightCounts(s: str) -> tuple:
l = 0
r = 0
for c in s:
if c == '(':
l += 1
elif c == ')':
if l == 0:
r += 1
else:
l -= 1
return l, r
def isValid(s: str):
count = 0 # number of '(' - # of ')'
for c in s:
if c == '(':
count += 1
elif c == ')':
count -= 1
if count < 0:
return False
return True # count == 0
ans = []
def dfs(s: str, start: int, l: int, r: int) -> None:
if l == 0 and r == 0 and isValid(s):
ans.append(s)
return
for i in range(start, len(s)):
if i > start and s[i] == s[i - 1]:
continue
if r > 0 and s[i] == ')': # delete s[i]
dfs(s[:i] + s[i + 1:], i, l, r - 1)
elif l > 0 and s[i] == '(': # delete s[i]
dfs(s[:i] + s[i + 1:], i, l - 1, r)
l, r = getLeftAndRightCounts(s)
dfs(s, 0, l, r)
return ans
Watch Tutorial
Checkout more Solutions here