Remove Invalid Parentheses
Table of Contents + −
A string of brackets can be broken in many ways. Some have one extra bracket. Some have many. This question asks you to fix the string by throwing away as few brackets as possible. The hard part is the words “as few as possible”. You cannot just delete everything until it looks fine. You have to find the smallest cut.
🎯 The Problem
You get a string of letters and round brackets that may be broken. You must make it valid with the fewest removals.
- A string is valid when every open bracket has a matching close bracket in the right order.
- The brackets in the input may not match up.
- Remove the smallest number of brackets so the string becomes valid.
- Return every distinct valid string you can reach with that smallest number of removals.
- For
()())()there is one extra close bracket, so you remove exactly one. - Two different removals both give a valid result.
Input: s = "()())()"Output: ["(())()", "()()()"]
Explanation: The string has one extra ")".Removing it in two spots gives two valid answers.You return all answers, and you never remove more brackets than you truly need.
This diagram shows where the string breaks. We walk left to right and count open brackets that are still waiting for a partner.
🐢 Approach 1: BFS Level by Level (Brute Force)
The idea in one line: try all one-removal strings, then all two-removal strings, and stop at the first valid level.
The idea:
- BFS means breadth-first search.
- It explores all strings needing one removal first, then two, and so on.
- So the first valid level it reaches uses the fewest removals.
How it works:
- Start with the original string. If it is already valid, you are done with zero removals.
- Otherwise build every string you can make by deleting one bracket. That is the next level.
- Check all of those. The moment any string in a level is valid, stop.
- Collect every valid string in that same level and ignore deeper levels.
Why it is weak:
- Each level creates a huge pile of new strings.
- Many of them repeat, so you must keep a set of seen strings.
- For long strings this uses a lot of memory and time.
Here is the BFS code for that idea:
from collections import deque
def remove_invalid_parentheses(s): def valid(text): balance = 0 for ch in text: if ch == "(": balance += 1 elif ch == ")": balance -= 1 if balance < 0: return False return balance == 0
queue = deque([s]) seen = {s} answer = [] found = False
while queue: text = queue.popleft() if valid(text): answer.append(text) found = True if found: continue for i, ch in enumerate(text): if ch in "()": nxt = text[:i] + text[i + 1:] if nxt not in seen: seen.add(nxt) queue.append(nxt) return answer⚡ Approach 2: Backtracking With a Removal Budget (Best)
The idea in one line: count exactly how many brackets to remove first, then remove only that many.
The idea:
- Backtracking means try a choice, go deeper, and undo it if it does not help.
- Scan the string once to find the budget: the extra opens and the extra closes.
- An extra close is a
)with no open bracket waiting for it.
How it works:
- After the scan, the leftover open count is the extra opens.
- Walk the string position by position. At each bracket, choose to remove it or keep it.
- Remove it only if budget for that kind remains.
- Track how many opens are still waiting. If that count drops below zero, stop the path early.
- At the end, if both budgets are zero and the string is balanced, save it.
- Use a set to avoid duplicate answers.
Why it is fast:
- The budget stops us from removing too much.
- We never explore paths that delete more brackets than needed.
- The negative-balance check prunes broken paths the moment they break.
This diagram shows the decision tree at the first few characters of ()())(). At each bracket we either remove it or keep it.
Steps to Solve
- Scan the string once and count how many open brackets and close brackets must be removed.
- Start a backtracking walk from position zero with those two removal budgets.
- At each open bracket, try removing it if the open budget is still positive, then try keeping it.
- At each close bracket, try removing it if the close budget is still positive, then try keeping it.
- Track the balance of kept brackets. If it drops below zero, stop that path early.
- At the end of the string, if both budgets are zero and the balance is zero, save the built string.
- Use a set so each valid answer appears only once.
This Python version counts the budgets, then backtracks, and stores answers in a set so duplicates disappear on their own.
def remove_invalid_parentheses(s): open_rem = 0 # extra "(" to remove close_rem = 0 # extra ")" to remove for c in s: # count what must be removed if c == "(": open_rem += 1 elif c == ")": if open_rem > 0: open_rem -= 1 # this ) matches a waiting ( else: close_rem += 1 # no open waiting, extra )
found = set()
def backtrack(pos, open_rem, close_rem, open_count, path): if pos == len(s): if open_rem == 0 and close_rem == 0 and open_count == 0: found.add(path) return c = s[pos] # option 1: remove this bracket if budget allows if c == "(" and open_rem > 0: backtrack(pos + 1, open_rem - 1, close_rem, open_count, path) elif c == ")" and close_rem > 0: backtrack(pos + 1, open_rem, close_rem - 1, open_count, path) # option 2: keep this character if c == "(": backtrack(pos + 1, open_rem, close_rem, open_count + 1, path + c) elif c == ")": if open_count > 0: # only keep ) if an open waits backtrack(pos + 1, open_rem, close_rem, open_count - 1, path + c) else: backtrack(pos + 1, open_rem, close_rem, open_count, path + c)
backtrack(0, open_rem, close_rem, 0, "") return sorted(found)
s = "()())()"print(remove_invalid_parentheses(s))The output of the above code will be:
['(())()', '()()()']Let us walk through the Python version line by line and see why each piece is there.
The first loop counts the budget. We add one to open_rem for every (. For every ) we check if an open is waiting. If yes, this close matches it, so we lower open_rem. If no open is waiting, this close is extra, so we raise close_rem. After the loop, open_rem holds the leftover opens that never got a partner. So now we know exactly how many of each kind to delete.
Inside backtrack, the line if pos == len(s) checks if we reached the end. We only save the path when both budgets are zero and open_count is zero. That means we used our full budget and the brackets are balanced.
The line if c == "(" and open_rem > 0 is the remove choice for an open bracket. We skip the character and lower the open budget. The line elif c == ")" and close_rem > 0 is the same remove choice for a close bracket.
Then the keep choices add the character to path. The important guard is if open_count > 0 before keeping a ). This stops the balance from going negative. A negative balance means a close bracket appeared with no open waiting, which can never become valid. So we prune that path right there. That guard is what keeps the search fast.
⏱️ Time and Space Complexity
At each bracket we branch into a remove path and a keep path. So in the worst case the work grows like 2 to the power of n, where n is the length of the string. The budget and the balance guard cut many branches, so real strings run far faster. The BFS approach also explores many strings per level and stores a set of seen strings, so it uses more memory in practice.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| BFS level by level | O(2^n) worst case | O(2^n) for the seen set |
| Backtracking with budget | O(2^n) worst case | O(n) recursion depth |
Tip
The key insight to say out loud is the budget. Count the extra opens and closes first. Then your search removes exactly that many and not one more. That is what makes the answer minimal.
🧩 Key Takeaways
- ✅ Remove the smallest number of brackets, not just enough to look valid.
- ✅ Count the extra open and close brackets first to get a removal budget.
- ✅ At each bracket, try removing it and try keeping it, but only remove within budget.
- ✅ Stop a path early when the balance of kept brackets goes negative.
- ✅ Use a set so each valid string appears only once in the answer.
Check Your Knowledge
Test what you learned. Pick an answer for each question, then click Check.
- 1
What does this problem ask you to minimize?
Why: You must remove the fewest brackets possible to make the string valid.
- 2
Why does counting the budget first help the backtracking?
Why: The budget caps removals to the minimum, so paths that delete extra brackets are never explored.
- 3
When do we prune a path while keeping a close bracket?
Why: Keeping a ) when no open bracket is waiting makes the balance negative, which can never become valid.
- 4
Why use a set to store the answers?
Why: Different removal paths can build the same string, so a set keeps only distinct answers.