Remove Invalid Parentheses

hard string backtracking bfs

Problem

Given a string containing parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid. Return all unique results.

Inputs = "()())()"

Output["(())()", "()()()"]

def remove_invalid(s):
    def valid(t):
        c = 0
        for ch in t:
            if ch == '(': c += 1
            elif ch == ')':
                c -= 1
                if c < 0: return False
        return c == 0
    seen = {s}
    level = [s]
    while level:
        good = [t for t in level if valid(t)]
        if good: return good
        nxt = set()
        for t in level:
            for i, ch in enumerate(t):
                if ch in "()":
                    cand = t[:i] + t[i + 1:]
                    if cand not in seen:
                        seen.add(cand); nxt.add(cand)
        level = list(nxt)
    return [""]

function removeInvalid(s) {
  function valid(t) {
    let c = 0;
    for (const ch of t) {
      if (ch === '(') c++;
      else if (ch === ')') { if (--c < 0) return false; }
    }
    return c === 0;
  }
  const seen = new Set([s]);
  let level = [s];
  while (level.length) {
    const good = level.filter(valid);
    if (good.length) return good;
    const nxt = new Set();
    for (const t of level)
      for (let i = 0; i < t.length; i++)
        if (t[i] === '(' || t[i] === ')') {
          const c = t.slice(0, i) + t.slice(i + 1);
          if (!seen.has(c)) { seen.add(c); nxt.add(c); }
        }
    level = [...nxt];
  }
  return [""];
}

class Solution {
    boolean valid(String t) {
        int c = 0;
        for (char ch : t.toCharArray()) {
            if (ch == '(') c++;
            else if (ch == ')' && --c < 0) return false;
        }
        return c == 0;
    }
    public List<String> removeInvalidParentheses(String s) {
        Set<String> seen = new HashSet<>(); seen.add(s);
        List<String> level = new ArrayList<>(); level.add(s);
        while (!level.isEmpty()) {
            List<String> good = new ArrayList<>();
            for (String t : level) if (valid(t)) good.add(t);
            if (!good.isEmpty()) return good;
            Set<String> nxt = new HashSet<>();
            for (String t : level)
                for (int i = 0; i < t.length(); i++) {
                    char ch = t.charAt(i);
                    if (ch == '(' || ch == ')') {
                        String c = t.substring(0, i) + t.substring(i + 1);
                        if (seen.add(c)) nxt.add(c);
                    }
                }
            level = new ArrayList<>(nxt);
        }
        return Arrays.asList("");
    }
}

bool valid(string t) {
    int c = 0;
    for (char ch : t) {
        if (ch == '(') c++;
        else if (ch == ')' && --c < 0) return false;
    }
    return c == 0;
}
vector<string> removeInvalidParentheses(string s) {
    unordered_set<string> seen{s};
    vector<string> level{s};
    while (!level.empty()) {
        vector<string> good;
        for (auto& t : level) if (valid(t)) good.push_back(t);
        if (!good.empty()) return good;
        unordered_set<string> nxt;
        for (auto& t : level)
            for (int i = 0; i < (int)t.size(); i++)
                if (t[i] == '(' || t[i] == ')') {
                    string c = t.substr(0, i) + t.substr(i + 1);
                    if (seen.insert(c).second) nxt.insert(c);
                }
        level.assign(nxt.begin(), nxt.end());
    }
    return {""};
}

Explanation

We must remove the fewest parentheses to make the string valid, and list every result that uses that minimum. The trick is to treat "number of removals" as distance and search level by level with BFS (breadth-first search).

We start with the original string as level 0. At each level we first check: does any string here already balance? The helper valid scans left to right, counting ( as +1 and ) as -1, and fails if the count ever goes negative or does not end at zero.

Because BFS explores all strings with 0 removals, then all with 1 removal, then 2, and so on, the first level that contains any valid string automatically uses the minimum number of removals. We return all valid strings from that level and stop.

If nothing is valid yet, we build the next level by deleting one parenthesis at a time from each current string. A seen set prevents revisiting the same string, which keeps the search from blowing up on duplicates.

Example: s = "()())()". Level 0 is invalid. After removing exactly one parenthesis, two valid strings appear: "(())()" and "()()()", so the minimum is 1 removal and both are returned.

Time: O(n · 2^n) worst case Space: O(2^n)