Skip to main content

26. Remove Invalid Parentheses

hardAsked at Meta

Generate all minimum-removal results to make parentheses valid — Meta's search query parser and structured-message sanitizer use exactly this BFS enumeration to recover gracefully from malformed user input at scale.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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

Constraints

  • 1 <= s.length <= 25
  • s consists of lowercase English letters and parentheses '(' and ')'

Examples

Example 1

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

Explanation: Both strings are valid with the minimum of one removal.

Example 2

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

Approaches

1. BFS level by level

BFS where each level tries removing one more character; stop at the first level that yields any valid string. Guarantees minimum removals and explores all possibilities at that depth.

Time
O(n * 2^n)
Space
O(n * 2^n)
function removeInvalidParentheses(s) {
  function isValid(str) {
    let count = 0;
    for (const c of str) {
      if (c === '(') count++;
      else if (c === ')') { if (--count < 0) return false; }
    }
    return count === 0;
  }
  const res = [], seen = new Set([s]);
  let queue = [s], found = false;
  while (queue.length) {
    const next = [];
    for (const cur of queue) {
      if (isValid(cur)) { res.push(cur); found = true; }
      if (found) continue;
      for (let i = 0; i < cur.length; i++) {
        if (cur[i] !== '(' && cur[i] !== ')') continue;
        const cand = cur.slice(0, i) + cur.slice(i+1);
        if (!seen.has(cand)) { seen.add(cand); next.push(cand); }
      }
    }
    if (found) break;
    queue = next;
  }
  return res.length ? res : [''];
}

Tradeoff:

2. DFS with pruning

First count how many '(' and ')' need removal; then DFS generating candidates, pruning when removal budget is exceeded.

Time
O(2^n)
Space
O(n)
function removeInvalidParentheses(s) {
  let leftRem = 0, rightRem = 0;
  for (const c of s) {
    if (c === '(') leftRem++;
    else if (c === ')') { if (leftRem > 0) leftRem--; else rightRem++; }
  }
  const res = new Set();
  function dfs(i, open, lRem, rRem, cur) {
    if (i === s.length) {
      if (lRem === 0 && rRem === 0 && open === 0) res.add(cur);
      return;
    }
    const c = s[i];
    if (c === '(' && lRem > 0) dfs(i+1, open, lRem-1, rRem, cur);
    if (c === ')' && rRem > 0) dfs(i+1, open, lRem, rRem-1, cur);
    if (c === '(') {
      dfs(i+1, open+1, lRem, rRem, cur+c);
    } else if (c === ')') {
      if (open > 0) dfs(i+1, open-1, lRem, rRem, cur+c);
    } else {
      dfs(i+1, open, lRem, rRem, cur+c);
    }
  }
  dfs(0, 0, leftRem, rightRem, '');
  return [...res];
}

Tradeoff:

Meta-specific tips

Meta focuses on whether you enumerate all unique results without duplicates. The BFS approach is simpler to reason about and easier to code correctly under pressure — prefer it. Mention that DFS with pruning is faster in practice because it avoids the seen-set overhead. Always count the minimum removals needed first rather than trying arbitrary deletions.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Remove Invalid Parentheses and other Meta interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →