301. Remove Invalid Parentheses

301

HardBacktrackingDFS over keep/remove choices bounded by counted removalsBacktracking with precomputed minimum removals

Remove Invalid Parentheses

Given a string s containing letters and parentheses, remove the minimum number of invalid parentheses so that the resulting string is valid. Return all unique valid strings achievable with the minimum removals.

Open official problem prompt ↗

In plain English

Find all shortest-edit-distance valid strings reachable by deleting only parentheses, deleting as few as possible.

Picture it like this

Like fixing an unbalanced set of brackets in a document by erasing the fewest brackets; you first tally how many extras exist, then try each way of erasing exactly that many and keep the balanced results.

Example

Input: s = "()())"
Output: ["(())","()()"]
Why: There is one extra ')'. Removing exactly one ')' yields the valid strings (()) and ()(); both use the minimum of one removal.

Constraints

1 <= s.length <= 25s consists of lowercase letters and the characters '(' and ')'There are at most 20 parentheses in s

Pattern lesson

See the pattern, then code

Backtracking with precomputed minimum removals

↗

Backtracking

Generate every valid combination, permutation, partition, or configuration.. First scan counts the surplus '(' and ')' that must go; then DFS decides keep-or-remove per parenthesis, using those two budgets and an open counter to reject invalid or over-removed branches.

New words, made simpleKnow these before the algorithm

Unmatched paren: A '(' with no later ')' or a ')' with no earlier unmatched '(' that must be removed.
open_count: How many '(' kept so far are still waiting to be closed; must never go negative.
Removal budget: l_rem and r_rem, the exact counts of '(' and ')' that must be deleted.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

BFS by removal count

Correct and finds the minimum level, but generates and validates huge candidate sets.

Try removing 0 chars, then 1, then 2, ... generating all candidates at each level until a valid one appears.

Time O(2^n * n)Space O(2^n)

Best choiceDFS with precounted removals

Explores only branches consistent with the minimum removal count and dedupes with a set.

Count required removals first, then branch keep/remove within that exact budget, pruning on negative open or budget.

Time O(2^n)Space O(n)

The rule we keep true

Invariant

At every recursion, path is a prefix built from the first index characters, open_count equals its number of unclosed '(', and l_rem/r_rem are the removals still owed.

Why this is correct

Reasoning

The initial scan computes the minimum removals precisely; the DFS only reaches the base case when both budgets hit zero and open_count is zero, guaranteeing a balanced string that used exactly the minimum deletions. The set removes duplicate strings produced by equivalent removals.

The algorithm in three movesSay these aloud before coding

1Scan once to count l_rem (unmatched '(') and r_rem (unmatched ')')

l_rem=0, r_rem=1 after scan

2DFS over each character; letters are always kept

remove ')' at idx1 -> '(())'

3For '(' branch on removing (l_rem-1) or keeping (open+1)

remove ')' at idx3 or idx4 -> '()()'

4For ')' branch on removing (r_rem-1) or keeping (open-1)

5At the end accept when open==0 and both budgets are exhausted; use a set to dedupe

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Reads = ()())

2 · AskHow many surplus parens?

3 · Update stateleft=0, right=1

4 · ResultMust remove one ')'

Key takeaway

The string ()()) with the surplus closing parenthesis at the end highlighted.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-11Count mandatory removals
One pass finds surplus '(' (left) and surplus ')' (right) that must be deleted.
2
Lines 14-19Prune and accept
Reject over-removal or negative open; accept only fully balanced strings with both budgets spent.
3
Lines 20-30Keep-or-remove branches
Parentheses branch into remove (spend budget) and keep (adjust open); letters are always kept.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Already valid string returns itself with zero removals
String of only letters returns itself
All parentheses invalid, e.g. ')))', reduces to the empty string ''
Multiple removal spots collapsing to the same string are deduped

Common beginner mistakes

Not deduping, producing repeated identical strings
Letting open_count go negative and still recording
Removing more than the minimum by not bounding with l_rem/r_rem
Miscounting right by decrementing left when it is already zero

Check your understanding

Why must we compute l_rem and r_rem before the DFS instead of just minimizing during search?

PyPython 3 · solution.py

Optimal

1class Solution:2    def removeInvalidParentheses(self, s: str) -> list[str]:3        left = right = 04        for c in s:5            if c == '(':6                left += 17            elif c == ')':8                if left > 0:9                    left -= 110                else:11                    right += 112        res: set[str] = set()1314        def backtrack(index: int, path: str, open_count: int, l_rem: int, r_rem: int) -> None:15            if l_rem < 0 or r_rem < 0 or open_count < 0:16                return17            if index == len(s):18                if open_count == 0 and l_rem == 0 and r_rem == 0:19                    res.add(path)20                return21            c = s[index]22            if c == '(':23                backtrack(index + 1, path, open_count, l_rem - 1, r_rem)24                backtrack(index + 1, path + c, open_count + 1, l_rem, r_rem)25            elif c == ')':26                backtrack(index + 1, path, open_count, l_rem, r_rem - 1)27                backtrack(index + 1, path + c, open_count - 1, l_rem, r_rem)28            else:29                backtrack(index + 1, path + c, open_count, l_rem, r_rem)3031        backtrack(0, '', 0, left, right)32        return list(res)

Time complexityO(2^n)Optimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

MetaGoogleAmazon

Remove Invalid Parentheses

Remove Invalid Parentheses

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Backtracking