Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:

"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

Credits:
Special thanks to @hpplayer for adding this problem and creating all test cases.

An elegant BFS algorithm.

Each time we delete a ‘(‘ or ‘)’ and push it into the queue, then check its validity. if the current string is not valid and the result set is empty, delete a ‘(‘ or ‘)’ in current string and push it into the queue.

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        //BFS
        queue<pair<string, int> > q;
        unordered_set<string> set;
        unordered_set<string> isVisited; // string is in q or not
        
        q.push(make_pair(s, 0));
        isVisited.insert(s);
        
        while(!q.empty()){
            int distance = q.front().second;
            string ss = q.front().first;
            q.pop();
            if(isValid(ss)){
                if(set.empty() || (*set.begin()).size() == ss.size()){
                    // same number of removal characters
                    set.insert(ss);    
                }
            }
            else{
                // ss is not valid
                if(!set.empty()){
                    // at least one answer has found, no need to push new string into queue
                    continue;
                }
                for(int i = 0; i < ss.size(); i++){
                    if(ss[i] != '(' && ss[i] != ')'){
                        // not a valid parenthese, ignore it
                        continue;
                    }
                    if(i > 0 && ss[i] == ss[i - 1]){
                        // duplicate results, skip them
                        continue;
                    }
                    string nextStr = ss.substr(0, i);
                    if(i + 1 < ss.size())
                        nextStr.append(ss.substr(i + 1, -1));
                    if(isVisited.count(nextStr) == 0){
                        // not visited
                        isVisited.insert(nextStr);
                        q.push(make_pair(nextStr, distance + 1));
                    }
                }
            }
        }
        vector<string> ans;
        for(auto it = set.begin(); it != set.end(); it++){
            ans.push_back(*it);
        }
        return ans;
    }
    bool isValid(string s){
        int count = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '(') count++;
            if(s[i] == ')') count--;
            if(count < 0) return false;
        }
        return count == 0;
    }
};