#301

Hard

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Remove Invalid Parentheses

Remove the minimum number of invalid parentheses to generate all possible valid strings efficiently using backtracking and BFS.

string backtracking breadth first search

Problem Statement

You are given a string containing letters and parentheses '(' and ')'. Your task is to remove the minimum number of invalid parentheses to make the string valid. Return all possible unique strings that are valid after removals.

Each valid string should have balanced parentheses, and you may return them in any order. For example, given s = "()())()", the valid outputs are ["(())()","()()()"]. Constraints include 1 <= s.length <= 25 and at most 20 parentheses in the string.

Examples

Example 1

Input: s = "()())()"

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

Example details omitted.

Example 2

Input: s = "(a)())()"

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

Example details omitted.

Example 3

Input: s = ")("

Output: [""]

Example details omitted.

Constraints

1 <= s.length <= 25
s consists of lowercase English letters and parentheses '(' and ')'.
There will be at most 20 parentheses in s.

Solution Approach

Backtracking with Pruning

Use recursive backtracking to explore each position where a parenthesis can be removed. Skip paths that produce strings with more removals than the current minimum or that repeat previous states.

Breadth-First Search Level Exploration

Use BFS to systematically remove parentheses level by level, guaranteeing that the first level producing valid strings corresponds to the minimal number of removals. Early termination prevents unnecessary deeper exploration.

Duplicate Avoidance and Validation

Use a set to store unique results and a validation function to check if a string is balanced. Only add strings that meet validity criteria and have the minimal removals to the result list.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is exponential in the number of parentheses due to exploring all removal combinations, but pruning and BFS early termination reduce the practical runtime. Space complexity is proportional to the number of unique states and recursion or BFS queue size.

What Interviewers Usually Probe

Looking for minimal removal and correctness rather than brute-force generation
Expect recognition of backtracking with pruning and BFS level-order exploration
Wants handling of duplicates and validation logic efficiently

Common Pitfalls or Variants

Common pitfalls

Failing to prune branches exceeding minimal removals increases runtime
Not handling duplicate strings leads to redundant results
Incorrect validation of parentheses causes invalid strings in output

Follow-up variants

Only remove '(' or only ')' to balance a string
Return count of valid strings instead of actual strings
Input contains additional characters like digits or special symbols

FAQ

What is the main strategy for Remove Invalid Parentheses?

Use backtracking with pruning and BFS to generate all unique valid strings with minimal removals.

How do I avoid duplicates in the output?

Store results in a set and only add strings that pass validation to ensure uniqueness.

Can this be solved without recursion?

Yes, BFS level-order exploration allows iterative generation while still guaranteeing minimal removals.

How does pruning improve performance?

Pruning stops exploration of paths that exceed the current minimal number of removals, reducing unnecessary computation.

What is the pattern used in this problem?

The problem follows a backtracking search with pruning pattern, exploring all valid parenthesis removal combinations efficiently.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        def dfs(i, l, r, lcnt, rcnt, t):
            if i == n:
                if l == 0 and r == 0:
                    ans.add(t)
                return
            if n - i < l + r or lcnt < rcnt:
                return
            if s[i] == '(' and l:
                dfs(i + 1, l - 1, r, lcnt, rcnt, t)
            elif s[i] == ')' and r:
                dfs(i + 1, l, r - 1, lcnt, rcnt, t)
            dfs(i + 1, l, r, lcnt + (s[i] == '('), rcnt + (s[i] == ')'), t + s[i])

        l = r = 0
        for c in s:
            if c == '(':
                l += 1
            elif c == ')':
                if l:
                    l -= 1
                else:
                    r += 1
        ans = set()
        n = len(s)
        dfs(0, l, r, 0, 0, '')
        return list(ans)

Continue Practicing

#126 word ladder ii #1096 brace expansion ii #297 serialize and deserialize binary tree