Remove Invalid Parentheses Solutions in C++

// Source : https://leetcode.com/problems/remove-invalid-parentheses/
// Author : Hao Chen
// Date   : 2015-11-11



#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

//DFS 
void removeInvalidParenthesesHelper(string& s, int index, int pair,
                                    int remove_left, int remove_right, 
                                    string solution, unordered_set<string>& result) {

    char ch = s[index];

    //recusive ending 
    if ( ch == '\0' ) {
        if (pair==0 && remove_left==0 && remove_right==0 ) {
            result.insert(solution);
        }
        return;
    }
    //other char, move to next one
    if ( ch != '(' && ch != ')' ) {
        removeInvalidParenthesesHelper(s, index+1, pair, remove_left, remove_right, solution+ch, result);
        return;
    }
    
    //if we meet left one, and we need remove left one, 
    //then we have two choices : remove it, OR keep it.
    if ( ch == '(' ) {
        //revmoe it
        if (remove_left > 0 ) { 
            removeInvalidParenthesesHelper(s, index+1, pair, remove_left-1, remove_right, solution, result);
        }
        //keep it
        removeInvalidParenthesesHelper(s, index+1, pair+1, remove_left, remove_right, solution+ch, result);
    }
    
    //if we meet right one, and we need to remove right one,
    //then we have two choices as well: remove it, or keep it if there are some left already.
    if ( ch == ')' ) {
        if (remove_right > 0 ) {
            removeInvalidParenthesesHelper(s, index+1, pair, remove_left, remove_right-1, solution, result);
        }
        if (pair > 0){
            removeInvalidParenthesesHelper(s, index+1, pair-1, remove_left, remove_right, solution+ch, result);
        }
    }


}

vector<string> removeInvalidParentheses(string s) {

    //Calculating how many left/right parentheses need be removed!
    int remove_left = 0, remove_right = 0;
    for(auto c : s) {
        if ( c == '(' ) {
            remove_left++;
        }else if ( c == ')' ){
            if (remove_left > 0) {
                remove_left--; // if we matched
            }else{
                remove_right++;
            }
        }
    }

    unordered_set<string> result;
    removeInvalidParenthesesHelper(s, 0, 0, remove_left, remove_right, "", result);
    return vector<string>( result.begin(), result.end() );
}


void printVector(vector<string> result) {
    for( int i=0; i<result.size(); i++) {
        cout << i << ") " << result[i] << endl;
    }
}


int main(int argc, char** argv) {
    string s = "()())()";
    if (argc>1) {
        s = argv[1];
    }
    cout << s << endl;
    printVector( removeInvalidParentheses(s) );
    
    return 0;
}

/// Source : https://leetcode.com/problems/remove-invalid-parentheses/description/
/// Author : liuyubobobo
/// Time   : 2018-11-02

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;


/// Brute Force
/// Time Complexity: O(2^n)
/// Space Complexity: O(n)
class Solution {

private:
    int n;
    int maxlen;

public:
    vector<string> removeInvalidParentheses(string s) {

        n = s.size();
        maxlen = 0;

        unordered_set<string> res;
        dfs(s, 0, 0, "", res);
        return vector<string>(res.begin(), res.end());
    }

private:
    void dfs(const string& s, int index, int left, const string& cur,
             unordered_set<string>& res){

        if(index == n){
            if(left == 0){
                if(cur.size() > maxlen){
                    res.clear();
                    maxlen = cur.size();
                }

                if(cur.size() == maxlen)
                    res.insert(cur);
            }
            return;
        }

        if(s[index] != '(' && s[index] != ')')
            dfs(s, index + 1, left, cur + s[index], res);
        else if(s[index] == '('){
            dfs(s, index + 1, left + 1, cur + s[index], res);
            if(cur.size() + n - (index + 1) >= maxlen)
                dfs(s, index + 1, left, cur, res);
        }
        else{
            if(left > 0)
                dfs(s, index + 1, left - 1, cur + s[index], res);
            if(cur.size() + n - (index + 1) >= maxlen)
                dfs(s, index + 1, left, cur, res);
        }
    }
};


void print_vec(const vector<string>& vec){

    cout << vec.size() << " : ";
    for(const string& e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    string s1 = "()())()";
    print_vec(Solution().removeInvalidParentheses(s1));
    // 6
    // (())() ()()()

    string s2 = "(a)())()";
    print_vec(Solution().removeInvalidParentheses(s2));
    // 7
    // (a())() (a)()()

    string s3 = ")(";
    print_vec(Solution().removeInvalidParentheses(s3));
    // 0

    string s4 = "n";
    print_vec(Solution().removeInvalidParentheses(s4));
    // 1
    // n

    string s5 = "x(";
    print_vec(Solution().removeInvalidParentheses(s5));
    // 1
    // x

    string s6 = "((";
    print_vec(Solution().removeInvalidParentheses(s6));
    // 0


    return 0;
}

/// Source : https://leetcode.com/problems/remove-invalid-parentheses/description/
/// Author : liuyubobobo
/// Time   : 2018-11-02

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;


/// Calculate how many '(' and ')' are there
/// int the result maximum len expression first
/// Time Complexity: O(2^n)
/// Space Complexity: O(n)
class Solution {

private:
    int n, maxlen;

public:
    vector<string> removeInvalidParentheses(string s) {

        n = s.size();

        int total_left = 0, total_right = 0, l = 0, r = 0;
        for(char c: s){
            if(c == '(') total_left ++;
            else if(c == ')') total_right ++;

            if(c == '(') l ++;
            else if(c == ')'){
                if(l > 0) l --;
                else r ++;
            }
        }

        int rem_left = total_left - l, rem_right = total_right - r;
//        cout << "rem_left : " << rem_left << " ; rem_right : " << rem_right << endl;
        maxlen = s.size() - l - r;

        unordered_set<string> res;
        dfs(s, 0, rem_left, rem_right, "", res);
        return vector<string>(res.begin(), res.end());
    }

private:
    void dfs(const string& s, int index, int rem_left, int rem_right,
             const string& cur, unordered_set<string>& res){

        if(cur.size() == maxlen){
            if(!rem_left && !rem_right)
                res.insert(cur);
            return;
        }

        if(index == n || cur.size() > maxlen)
            return;

        if(s[index] != '(' && s[index] != ')')
            dfs(s, index + 1, rem_left, rem_right, cur + s[index], res);
        else if(s[index] == '('){
            if(rem_left)
                dfs(s, index + 1, rem_left - 1, rem_right, cur + s[index], res);
            dfs(s, index + 1, rem_left, rem_right, cur, res);
        }
        else{
            if(rem_right && rem_right > rem_left)
                dfs(s, index + 1, rem_left, rem_right - 1, cur + s[index], res);
            dfs(s, index + 1, rem_left, rem_right, cur, res);
        }
    }
};


void print_vec(const vector<string>& vec){

    cout << vec.size() << " : ";
    for(const string& e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    string s1 = "()())()";
    print_vec(Solution().removeInvalidParentheses(s1));
    // 6
    // (())() ()()()

    string s2 = "(a)())()";
    print_vec(Solution().removeInvalidParentheses(s2));
    // 7
    // (a())() (a)()()

    string s3 = ")(";
    print_vec(Solution().removeInvalidParentheses(s3));
    // 0

    string s4 = "n";
    print_vec(Solution().removeInvalidParentheses(s4));
    // 1
    // n

    string s5 = "x(";
    print_vec(Solution().removeInvalidParentheses(s5));
    // 1
    // x

    string s6 = "((";
    print_vec(Solution().removeInvalidParentheses(s6));
    // 0

    string s7 = "(()";
    print_vec(Solution().removeInvalidParentheses(s7));
    // 2

    return 0;
}