2020-03-24

class Solution {
public:
    string minRemoveToMakeValid(string s) {
    stack<string> char_stack;
    stack<int> index_stack;
    int length = s.length();
    if (length == 0)
        return s;
    int begin = 0, end = 1;
    for (; end <= length; end++) {
        string sub_str = s.substr(end-1, 1);
        if (sub_str == ")") {
            if (char_stack.empty() && index_stack.empty()) {
                char_stack.push(sub_str);
                index_stack.push(end - 1);
            }

            else if (char_stack.top() == "(") {
                char_stack.pop();
                index_stack.pop();
            }
            else {
                char_stack.push(sub_str);
                index_stack.push(end - 1);
            }
        }
        else if (sub_str == "(") {
            char_stack.push(sub_str);
            index_stack.push(end - 1);
        }
        else
            continue;

    }
    string new_str;
    if (char_stack.empty() && index_stack.empty())
        new_str= s;
    else {
        
        stack<int> re_index_stack;
        while (!index_stack.empty()) {
            re_index_stack.push(index_stack.top());
            index_stack.pop();
        }
            
        end = 1;

        for (; end <= length; end++) {
            //cout << end<<endl;
            if (!re_index_stack.empty()) {
                if ((end - 1) == re_index_stack.top()) {
                    re_index_stack.pop();
                    continue;
                }

                else {
                    new_str += s.substr(end - 1, 1);
                }
            }

            else {
                new_str += s.substr(end - 1, 1);
            }   
        }
    
        
    }
    return new_str;
    }
};