Remove Invalid Parentheses: BFS vs DFS Backtracking

Problem Statement#

You are given a string s that contains lowercase letters and parentheses (( and )). Remove the minimum number of invalid parentheses to make the string valid, and return all unique results.

For s = "()())" the answer is ["(())", "()()"]. For s = "(a)())()" the answer is ["(a())()", "(a)()()"]. For s = ")(" the answer is [""]. The output must contain only valid strings achievable with the minimum number of removals.

Why This Problem Matters#

LeetCode 301 is a Meta-favorite hard-tier problem. It tests three skills simultaneously: balanced-parentheses validation, BFS/DFS state exploration, and the cleverness to compute the minimum removal count up front so DFS does not waste cycles. Candidates who can deliver the DFS-with-quotas solution in 30 minutes signal senior-level recursion mastery.

The problem also shows up in code linters and IDE auto-fixers — the algorithmic core of "suggest the smallest fix to make this expression parse" is exactly this.

The Core Insight (decision tree / state space)#

There are two clean approaches:

BFS approach. Treat the string as a node in a graph; a directed edge connects s to s' if s' is obtained by removing one parenthesis from s. BFS from the original string. The first level at which any valid string appears is the minimum removal count, and we collect every valid string at that level. We never expand past that level, which is the pruning that makes BFS efficient.

DFS with quotas approach. First, scan the string once to compute open_rem and close_rem — the minimum number of ( and ) we must remove. Then DFS with state (idx, open_count, close_count, open_rem, close_rem, current). At each character, we either keep it or (if it is a parenthesis with quota remaining) remove it. Validity is enforced incrementally with open_count >= close_count. At the end, if both quotas are exhausted, record current in a deduplication set.

DFS-with-quotas is asymptotically optimal because it never explores branches that cannot reach a valid state with the minimum number of removals.

Visual Dry Run (recursion tree)#

For s = "()())":

Computing quotas: scan left-to-right with open counter. After scanning we get open_rem = 0, close_rem = 1.

DFS state (idx, open, close, oRem, cRem, curr)
(0, 0, 0, 0, 1, "")
  keep '(' -> (1, 1, 0, 0, 1, "(")
    keep ')' -> (2, 1, 1, 0, 1, "()")
      keep '(' -> (3, 2, 1, 0, 1, "()(")
        keep ')' -> (4, 2, 2, 0, 1, "()()")
          remove ')' -> (5, 2, 2, 0, 0, "()()") -> VALID
          keep ')' -> (5, 2, 3, 0, 1, "()())") invalid (open<close), skipped
        remove ')' -> (4, 2, 1, 0, 0, "()(") cRem=0 forces keep next ')'
          keep ')' -> (5, 2, 2, 0, 0, "()()") -> VALID (duplicate, dedup'd)

Both branches converge to ()() and (()) after the deduplication.

Solution (Optimal) — Python + JavaScript with backtracking template, complexity#

def removeInvalidParentheses(s):
    open_rem = close_rem = 0
    for c in s:
        if c == '(':
            open_rem += 1
        elif c == ')':
            if open_rem > 0:
                open_rem -= 1
            else:
                close_rem += 1
 
    result = set()
 
    def backtrack(idx, opened, closed, o_rem, c_rem, current):
        if idx == len(s):
            if o_rem == 0 and c_rem == 0:
                result.add(current)
            return
        ch = s[idx]
        # Option 1: remove this paren
        if ch == '(' and o_rem > 0:
            backtrack(idx + 1, opened, closed, o_rem - 1, c_rem, current)
        elif ch == ')' and c_rem > 0:
            backtrack(idx + 1, opened, closed, o_rem, c_rem - 1, current)
        # Option 2: keep this character
        if ch == '(':
            backtrack(idx + 1, opened + 1, closed, o_rem, c_rem, current + ch)
        elif ch == ')':
            if opened > closed:
                backtrack(idx + 1, opened, closed + 1, o_rem, c_rem, current + ch)
        else:
            backtrack(idx + 1, opened, closed, o_rem, c_rem, current + ch)
 
    backtrack(0, 0, 0, open_rem, close_rem, '')
    return list(result) if result else ['']

function removeInvalidParentheses(s) {
  let openRem = 0, closeRem = 0;
  for (const c of s) {
    if (c === '(') openRem++;
    else if (c === ')') {
      if (openRem > 0) openRem--;
      else closeRem++;
    }
  }
  const result = new Set();
  const backtrack = (idx, opened, closed, oRem, cRem, current) => {
    if (idx === s.length) {
      if (oRem === 0 && cRem === 0) result.add(current);
      return;
    }
    const ch = s[idx];
    if (ch === '(' && oRem > 0) {
      backtrack(idx + 1, opened, closed, oRem - 1, cRem, current);
    } else if (ch === ')' && cRem > 0) {
      backtrack(idx + 1, opened, closed, oRem, cRem - 1, current);
    }
    if (ch === '(') {
      backtrack(idx + 1, opened + 1, closed, oRem, cRem, current + ch);
    } else if (ch === ')') {
      if (opened > closed) backtrack(idx + 1, opened, closed + 1, oRem, cRem, current + ch);
    } else {
      backtrack(idx + 1, opened, closed, oRem, cRem, current + ch);
    }
  };
  backtrack(0, 0, 0, openRem, closeRem, '');
  return result.size ? [...result] : [''];
}

Complexity: O(2^n) in the worst case for both BFS and DFS-with-quotas, but the quotas dramatically prune the DFS tree. Space is O(n) for recursion plus the dedup set.

Common Mistakes#

• Skipping the quota precomputation. Without open_rem and close_rem, the DFS explores far too many branches.
• Forgetting to enforce opened > closed before keeping a ). This is the validity guard during construction.
• Using a list instead of a set to collect results — duplicates sneak in because the same final string can be reached via different removal sequences.
• Returning an empty list for s = ")(". The expected output is [""], the empty string.

Interview Tips#

• Lead with the quota idea: "I'll first scan the string to compute the minimum number of ( and ) removals, then DFS with those quotas as state."
• Mention the BFS alternative as a fallback. Interviewers like seeing both approaches and the tradeoff (BFS is simpler, DFS with quotas is faster).
• Walk through "()())" to demonstrate the validity guard opened > closed.
• Note the dedup set requirement; it is a frequent source of bugs.

Follow-up Questions#

• LeetCode 1249 (Minimum Remove to Make Valid Parentheses): only return one valid string with the minimum removals.
• LeetCode 22 (Generate Parentheses): generate all valid parentheses of length 2n.
• Add support for square or curly brackets — same algorithm with multiple counters.
• What if there are also characters [, ], {, }? Generalize to a stack-based validator.

Key Takeaways#

• Remove Invalid Parentheses is a Meta-favorite hard problem; both BFS and DFS-with-quotas solve it.
• Compute the minimum removal quotas up front; this is the most impactful pruning.
• Enforce opened > closed while constructing to avoid invalid prefixes.
• Use a set to deduplicate; multiple removal sequences reach the same string.
• Edge case s = ")(" returns [""], not an empty list.
• The same template generalizes to multi-bracket validators and code linters.

Sources:

• Remove Invalid Parentheses - LeetCode
• 301. Remove Invalid Parentheses - In-Depth Explanation