1
var removeInvalidParentheses = function (s) {
2
  const isValid = (s) => {
3
    const stack = [];
4
    for (let c of s) {
5
      if (c == "(") stack.push(c);
6
      else if (c == ")") {
7
        if (stack.length && stack.at(-1) == "(") stack.pop();
8
        else return false;
9
      }
10
    }
11
    return stack.length == 0;
12
  };
13

14
  const Q = [s],
15
    vis = new Set([s]),
16
    ans = [];
17
  let found = false;
18
  while (Q.length) {
19
    const top = Q.shift();
20
    if (isValid(top)) {
21
      ans.push(top);
22
      found = true;
23
    }
24
    if (found) continue;
25
    for (let i = 0; i < top.length; i++) {
26
      if (!"()".includes(top[i])) continue;
27

28
      const str = top.slice(0, i) + top.slice(i + 1);
29
      if (!vis.has(str)) {
30
        Q.push(str);
31
        vis.add(str);
32
      }
33
    }
34
  }
35
  if (ans.length == 0) return [""];
36
  return ans;
37
};