301. 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 ).

Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")("
Output: [""]

// BFS
bool isValid(const string& str) {
    int cnt = 0;
    for (char ch : str) {
        if (ch == '(') ++cnt;
        else if (ch == ')' && --cnt < 0) return false;
    }
    return cnt == 0;
}
vector<string> removeInvalidParentheses(string s) {
    vector<string> res;
    unordered_set<string> visited({s});
    queue<string> q({s});
    bool found = false;
    while (!q.empty()) {
        string t = q.front(); q.pop();
        if (isValid(t)) {
            res.push_back(t);
            found = true;
        }
        if (found) continue;
        // Remove one char from the t string
        for (int i = 0; i < t.length(); ++i) {
            if (t[i] != '(' && t[i] != ')') continue;
            string new_str = t.substr(0, i) + t.substr(i + 1);
            if (!visited.count(new_str)) {
                q.push(new_str);
                visited.insert(new_str);
            }
        }
    }
    return res;
}

// Recursion
bool isValid(const string& s) {
    int cnt = 0;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == '(') ++cnt;
        else if (s[i] == ')' && --cnt < 0) return false;
    }
    return cnt == 0;
}
void helper(string s, int start, int cnt1, int cnt2, vector<string>& res) {
    if (cnt1 == 0 && cnt2 == 0) {
        if (isValid(s)) res.push_back(s);
        return;
    }
    for (int i = start; i < s.length(); ++i) {
        if (i != start && s[i] == s[i - 1]) continue;
        if (cnt1 > 0 && s[i] == '(') {
            helper(s.substr(0, i) + s.substr(i + 1), i, cnt1 - 1, cnt2, res);
        }
        if (cnt2 > 0 && s[i] == ')') {
            helper(s.substr(0, i) + s.substr(i + 1), i, cnt1, cnt2 - 1, res);
        }
    }
}
vector<string> removeInvalidParentheses(string s) {
    vector<string> res;
    int cnt1 = 0, cnt2 = 0; // cnt1: surplus number of (, cnt2: surplus number of )
    // Calculate cnt1 and cnt2
    for (char ch : s) {
        cnt1 += (ch == '(');
        if (cnt1 == 0) cnt2 += (ch == ')');
        else cnt1 -= (ch == ')');
    }
    helper(s, 0, cnt1, cnt2, res);
    return res;
}

// Optimized Recursion
void helper(string s, int start, int last_del, const string& p, vector<string>& res) {
    int cnt = 0;
    for (int i = start; i < s.length(); ++i) {
        if (s[i] == p[0]) ++cnt;
        else if (s[i] == p[1]) --cnt;
        if (cnt >= 0) continue;
        // Delete extra p[1]
        for (int j = last_del; j <= i; ++j) {
            if (s[j] == p[1] && (j == last_del || (s[j] != s[j - 1]))) {
                helper(s.substr(0, j) + s.substr(j + 1), i, j, p, res);
            }
        }
        return; // if the program runs to here, no need to reverse to delete extra p[0]
    }
    // Delete extra p[0]
    string rev = string(s.rbegin(), s.rend());
    if (p[0] == '(') helper(rev, 0, 0, ")(", res);
    else res.push_back(rev);
}
vector<string> removeInvalidParentheses(string s) {
    vector<string> res;
    helper(s, 0, 0, "()", res);
    return res;
}