Skip to content

301. Remove Invalid Parentheses

On LeetCode ->

Problem

Remove the fewest parentheses from s so that every prefix has at least as many opening as closing parentheses and the final counts match. Keep all letters and return every unique optimal result.

s = "()())()" -> remove 1 -> {"(())()", "()()()"}

Key trick

First count exactly how many unmatched opening and closing parentheses must be removed, then backtrack using those removal quotas while tracking the current balance.

Trap

  • Equal total counts are insufficient because no prefix may have a negative balance.
  • Letters must always be kept.
  • Different removal choices can produce duplicate strings.
  • Every backtracking mutation must be undone before returning.

Why is it interesting?

It combines greedy preprocessing with constrained backtracking, greatly reducing the search space while guaranteeing minimum removals.

Python solution

class Solution:
    def removeInvalidParentheses(self, s: str) -> list[str]:
        left_rem = right_rem = 0

        # Determine the exact minimum removals of each parenthesis type.
        for ch in s:
            if ch == "(":
                left_rem += 1
            elif ch == ")":
                if left_rem:
                    left_rem -= 1
                else:
                    right_rem += 1

        res = set()
        path = []
        n = len(s)

        def backtrack(i: int, balance: int, left: int, right: int) -> None:
            if left + right > n - i:
                return

            if i == n:
                if balance == 0 and left == 0 and right == 0:
                    res.add("".join(path))
                return

            ch = s[i]

            if ch == "(":
                # Remove this opening parenthesis.
                if left:
                    backtrack(i + 1, balance, left - 1, right)

                # Keep it.
                path.append(ch)
                backtrack(i + 1, balance + 1, left, right)
                path.pop()

            elif ch == ")":
                # Remove this closing parenthesis.
                if right:
                    backtrack(i + 1, balance, left, right - 1)

                # Keep it only if an opening parenthesis is available.
                if balance:
                    path.append(ch)
                    backtrack(i + 1, balance - 1, left, right)
                    path.pop()

            else:
                # Letters cannot be removed.
                path.append(ch)
                backtrack(i + 1, balance, left, right)
                path.pop()

        backtrack(0, 0, left_rem, right_rem)
        return list(res)

Time complexity: \(O(n2^p)\) in the worst case, where \(p\) is the number of parentheses.

Space complexity: \(O(n + Rn)\), including recursion, the current path, and \(R\) returned strings.

Comment on my solution

  • In the first version, the letter branch appends a letter and immediately returns without popping it. The leaked letter remains in cur when earlier recursion frames explore other branches, producing strings that are not subsequences of the input.
  • In the second version, the letter is popped correctly, but execution then falls through. Because the following else belongs to the parenthesis check, a letter is also processed as if it were a closing parenthesis.
  • Using elif or returning after processing a letter fixes the control-flow bug.
  • A balance integer is simpler than cur_stack.
  • Computing the required removals first avoids tracking removed_min across all valid candidates.
  • A set provides direct result deduplication instead of repeated linear membership checks in a list.
# Wrong Answer: 56/129 testcases passed
# "(a)())()"
# output: ["a(a())()","a(a)()()"]
# expected: ["(a())()","(a)()()"]
class Solution:
    def removeInvalidParentheses(self, s: str) -> list[str]:
        n = len(s)
        cur_stack = [] # keep cur left parenthese not yet closed
        cur = []
        removed_min = float("inf")
        res = []

        # i current index in s
        def backtrack(i):
            nonlocal removed_min
            nonlocal res
            if i == n:
                if cur_stack:
                    return
                removed = n - len(cur)
                if removed == removed_min:
                    if "".join(cur) not in res:
                        res.append("".join(cur))
                elif removed < removed_min:
                    removed_min = removed
                    res = ["".join(cur)]
                return

            if s[i].isalpha():
                cur.append(s[i])
                return backtrack(i + 1)

            if s[i] == "(":
                # Remove (
                backtrack(i + 1)
                # Keep (
                cur_stack.append("(")
                cur.append("(")
                backtrack(i + 1)
                cur_stack.pop()
                cur.pop()
            else:
                if not cur_stack:
                    # Remove )
                    backtrack(i + 1)
                else:
                    # Remove )
                    backtrack(i + 1)
                    # keep )
                    cur_stack.pop()
                    cur.append(")")
                    backtrack(i + 1)
                    cur_stack.append("(")
                    cur.pop()

        backtrack(0)

        return res


# Wrong Answer: 41/129 testcases passed
# ")(f"
# output: ["()"]
# expected: ["f"]
class Solution:
    def removeInvalidParentheses(self, s: str) -> list[str]:
        n = len(s)
        cur_stack = [] # keep cur left parenthese not yet closed
        cur = []
        removed_min = float("inf")
        res = []

        # i current index in s
        def backtrack(i):
            nonlocal removed_min
            nonlocal res
            if i == n:
                if cur_stack:
                    return
                removed = n - len(cur)
                if removed == removed_min:
                    if "".join(cur) not in res:
                        res.append("".join(cur))
                elif removed < removed_min:
                    removed_min = removed
                    res = ["".join(cur)]
                return

            if s[i].isalpha():
                cur.append(s[i])
                backtrack(i + 1)
                cur.pop()

            if s[i] == "(":
                # Remove (
                backtrack(i + 1)
                # Keep (
                cur_stack.append("(")
                cur.append("(")
                backtrack(i + 1)
                cur_stack.pop()
                cur.pop()
            else:
                if not cur_stack:
                    # Remove )
                    backtrack(i + 1)
                else:
                    # Remove )
                    backtrack(i + 1)
                    # keep )
                    cur_stack.pop()
                    cur.append(")")
                    backtrack(i + 1)
                    cur_stack.append("(")
                    cur.pop()

        backtrack(0)

        return res

# WORKS but slow
# Updated after reading AI comments
class Solution:
    def removeInvalidParentheses(self, s: str) -> list[str]:
        n = len(s)
        cur_stack = [] # keep cur left parenthese not yet closed
        cur = []
        removed_min = float("inf")
        res = []

        # i current index in s
        def backtrack(i):
            nonlocal removed_min
            nonlocal res
            if i == n:
                if cur_stack:
                    return
                removed = n - len(cur)
                if removed == removed_min:
                    if "".join(cur) not in res:
                        res.append("".join(cur))
                elif removed < removed_min:
                    removed_min = removed
                    res = ["".join(cur)]
                return

            # Correctly group these conditions together
            # after reading AI comments
            if s[i].isalpha():
                cur.append(s[i])
                backtrack(i + 1)
                cur.pop()
            elif s[i] == "(":
                # Remove (
                backtrack(i + 1)
                # Keep (
                cur_stack.append("(")
                cur.append("(")
                backtrack(i + 1)
                cur_stack.pop()
                cur.pop()
            else:
                if not cur_stack:
                    # Remove )
                    backtrack(i + 1)
                else:
                    # Remove )
                    backtrack(i + 1)
                    # keep )
                    cur_stack.pop()
                    cur.append(")")
                    backtrack(i + 1)
                    cur_stack.append("(")
                    cur.pop()

        backtrack(0)

        return res