HardNo. 0301

Remove Invalid Parentheses — LeetCode 301 Python Solution

Topics
Breadth-First Search, String, Backtracking
Reading time
5 min

The problem

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid. Return a list of unique strings that are valid with the minimum number of removals.

Example

Input
s = "()())()"
Output
["(())()","()()()"]

Python solution

PythonSolution
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)

Complexity

Time
Exponential (worst case)
Space · auxiliary
O(depth)

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 301. Remove Invalid Parentheses is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0306Additive NumberMedium
0079Word SearchMedium
0093Restore IP AddressesMedium
0212Word Search IIHard
0257Binary Tree PathsEasy
0282Expression Add OperatorsHard

Frequently asked questions

How hard is LeetCode 301. Remove Invalid Parentheses?

LeetCode 301. Remove Invalid Parentheses is rated Hard on LeetCode.

What topics does LeetCode 301. Remove Invalid Parentheses cover?

LeetCode 301. Remove Invalid Parentheses is tagged Breadth-First Search, String and Backtracking on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.