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.

Remove Invalid Parentheses — LeetCode 301 Python Solution

HardBreadth-First SearchStringBacktracking

Problem: #301
Pattern: Backtracking
Reading time: 5 min
Source: leetcode.com

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

Python

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

Measure	Complexity
Time	Exponential (worst case)
Space	O(depth) auxiliary

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.

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.