Remove Invalid Parentheses — Solution in Python, Java & C++
Remove Invalid Parentheses solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Remove Invalid Parentheses is a hard coding problem on strings, breadth-first search and backtracking, asked in Amazon, Google, Meta and Rubrik interviews.
- Difficulty: Hard
- Topics: Strings, Breadth-First Search, Backtracking
- Asked at: Amazon, Google, Meta, Rubrik
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A string s holds lowercase letters and the brackets ( and ). It is valid when its brackets are balanced: reading left to right, no ) ever appears without an unmatched ( before it, and every ( is matched by the end. Letters are ignored.
Delete the minimum number of brackets so that the string becomes valid, and return every distinct valid string you can reach with that minimum number of deletions.
Return the strings sorted in ascending lexicographic order (by character code, so ( < ) < letters). If the only option is to delete every bracket and nothing is left, the answer is [""].
Example 1
Input: s = "(c)o)d(e)"
Output: ["(c)od(e)","(co)d(e)"]
Explanation: One `)` is surplus; deleting either of the first two gives a valid string.
Example 2
Input: s = "))("
Output: [""]
Example 3
Input: s = "x(()"
Output: ["x()"]
Explanation: Deleting either `(` produces the same string, which is listed once.
Constraints
1 <= s.length <= 25s consists of lowercase English letters and '(' and ')'There are at most 20 brackets in s
Hints for Remove Invalid Parentheses
Hint 1
One left-to-right pass tells you how many
(and how many)must be deleted: count the)that have no partner, and the(still open at the end.Hint 2
Search over the string with those two budgets: at each bracket either delete it (if its budget allows) or keep it, tracking how many
(are currently open.Hint 3
Never keep a
)when nothing is open, and accept a finished string only when both budgets are spent and nothing is open. Collect results in a set to remove duplicates, then sort.
How to solve Remove Invalid Parentheses
The minimum number of deletions is known in advance — a balance scan counts the unmatched ) and the leftover ( — so a depth-first search that spends exactly those budgets enumerates precisely the optimal strings.
Approach
- Scan
swith a counter:(increments it;)decrements it if positive, otherwise incrementsright(an unmatched)). At the end the counter isleft, the unmatched(. - DFS over positions
iwith state(open, left, right)and the string built so far. - At a letter, keep it. At
(: ifleft > 0, branch on deleting it; also branch on keeping it (open + 1). - At
): ifright > 0, branch on deleting it; ifopen > 0, branch on keeping it (open - 1). - At the end, record the built string if
open == left == right == 0. - Deduplicate with a set and sort the result.
Why it works
No valid string can be reached with fewer than left + right deletions: every unmatched ) found by the scan needs a ( before it that does not exist, and every leftover ( needs a later ). Conversely, the search keeps the running balance non-negative and requires it to end at zero, so every recorded string is valid, and it only records strings that used exactly the minimum budgets. Every optimal deletion set is one path of the search, so nothing is missed.
Complexity
- Time —
O(2^b · n) in the worst case for b brackets, far less in practice because the budgets prune most branches - Space —
O(n) recursion depth plus the output
Pitfalls
- Different deletion sets can yield the same string (
"x(()"→"x()"twice) — deduplicate. - Deleting more than the minimum also gives valid strings; they must not be reported.
- When the answer is to delete every bracket of a letter-free string, the result is a list holding the empty string, not an empty list.
Reference solution
Python
from typing import List
def removeInvalidParentheses(s: str) -> List[str]:
left = right = 0
for c in s:
if c == "(":
left += 1
elif c == ")":
if left > 0:
left -= 1
else:
right += 1
n = len(s)
found = set()
buf = []
def dfs(i, opened, l, r):
if i == n:
if l == 0 and r == 0 and opened == 0:
found.add("".join(buf))
return
c = s[i]
if c == "(":
if l > 0:
dfs(i + 1, opened, l - 1, r)
buf.append(c)
dfs(i + 1, opened + 1, l, r)
buf.pop()
elif c == ")":
if r > 0:
dfs(i + 1, opened, l, r - 1)
if opened > 0:
buf.append(c)
dfs(i + 1, opened - 1, l, r)
buf.pop()
else:
buf.append(c)
dfs(i + 1, opened, l, r)
buf.pop()
dfs(0, 0, left, right)
return sorted(found)Java
static void ripDfs(String s, int i, int opened, int l, int r, StringBuilder cur, TreeSet<String> found) {
if (i == s.length()) {
if (l == 0 && r == 0 && opened == 0) found.add(cur.toString());
return;
}
char c = s.charAt(i);
if (c == '(') {
if (l > 0) ripDfs(s, i + 1, opened, l - 1, r, cur, found);
cur.append(c);
ripDfs(s, i + 1, opened + 1, l, r, cur, found);
cur.setLength(cur.length() - 1);
} else if (c == ')') {
if (r > 0) ripDfs(s, i + 1, opened, l, r - 1, cur, found);
if (opened > 0) {
cur.append(c);
ripDfs(s, i + 1, opened - 1, l, r, cur, found);
cur.setLength(cur.length() - 1);
}
} else {
cur.append(c);
ripDfs(s, i + 1, opened, l, r, cur, found);
cur.setLength(cur.length() - 1);
}
}
public static String[] removeInvalidParentheses(String s) {
int left = 0, right = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') left++;
else if (c == ')') {
if (left > 0) left--;
else right++;
}
}
TreeSet<String> found = new TreeSet<>();
ripDfs(s, 0, 0, left, right, new StringBuilder(), found);
return found.toArray(new String[0]);
}C++
static void ripDfs(const string& s, int i, int opened, int l, int r, string& cur, set<string>& found) {
if (i == (int)s.size()) {
if (l == 0 && r == 0 && opened == 0) found.insert(cur);
return;
}
char c = s[i];
if (c == '(') {
if (l > 0) ripDfs(s, i + 1, opened, l - 1, r, cur, found);
cur.push_back(c);
ripDfs(s, i + 1, opened + 1, l, r, cur, found);
cur.pop_back();
} else if (c == ')') {
if (r > 0) ripDfs(s, i + 1, opened, l, r - 1, cur, found);
if (opened > 0) {
cur.push_back(c);
ripDfs(s, i + 1, opened - 1, l, r, cur, found);
cur.pop_back();
}
} else {
cur.push_back(c);
ripDfs(s, i + 1, opened, l, r, cur, found);
cur.pop_back();
}
}
vector<string> removeInvalidParentheses(string s) {
int left = 0, right = 0;
for (char c : s) {
if (c == '(') left++;
else if (c == ')') {
if (left > 0) left--;
else right++;
}
}
set<string> found;
string cur;
ripDfs(s, 0, 0, left, right, cur, found);
return vector<string>(found.begin(), found.end());
}JavaScript
var removeInvalidParentheses = function(s) {
var left = 0, right = 0;
for (var i = 0; i < s.length; i++) {
if (s[i] === "(") left++;
else if (s[i] === ")") {
if (left > 0) left--;
else right++;
}
}
var n = s.length;
var found = new Set();
var dfs = function(i, opened, l, r, cur) {
if (i === n) {
if (l === 0 && r === 0 && opened === 0) found.add(cur);
return;
}
var c = s[i];
if (c === "(") {
if (l > 0) dfs(i + 1, opened, l - 1, r, cur);
dfs(i + 1, opened + 1, l, r, cur + c);
} else if (c === ")") {
if (r > 0) dfs(i + 1, opened, l, r - 1, cur);
if (opened > 0) dfs(i + 1, opened - 1, l, r, cur + c);
} else {
dfs(i + 1, opened, l, r, cur + c);
}
};
dfs(0, 0, left, right, "");
return Array.from(found).sort();
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Breadth-First Search (BFS)