October 7Hard

Remove invalid parentheses

String
Backtracking
BFS

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. You may return the answer in any order.

Solution

def get_wrong(s):
    wrong = 0
    opened = 0
    for char in s:
        if char == "(":
            opened += 1
        elif char == ")":
            if opened:
                opened -= 1
            else:
                wrong += 1
    return wrong + opened

class Solution:
    def removeInvalidParentheses(self, s: str) -> list[str]:
        wrong = get_wrong(s)
        res = []

        @cache
        def solve(curr_s, n):
            i = len(curr_s) + n
            if i == len(s):
                if not get_wrong(curr_s):
                    res.append(curr_s)
                return

            solve(curr_s + s[i], n)
            if (s[i] == "(" or s[i] == ")") and n < wrong:
                solve(curr_s, n + 1)

        solve("", 0)
        return res