tiktokOA 1249. Minimum Remove to Make Valid Parentheses

过了但很慢

class Solution {
public:
    string minRemoveToMakevalid(string s) {
        string res = "";
        stack left;
        int n = s.length();
        for(int i = 0; i < n; i++){
            if(s[i] == '('){
                left.push(i);
                res += ' ';
            }
            else if(s[i] == ')'){
                if(!left.empty()){
                    int index = left.top();
                    left.pop();
                    res += ')';
                    res[index] = '(';
                }
                else
                    res += ' ';
            }
            else
                res += s[i];
        }
        for(int i = 0; i < res.length(); i++){
            if(res[i] == ' '){
                if(i < res.length()-1)
                    res = res.substr(0,i) + res.substr(i+1, res.length()-i-1);
                else
                    res = res.substr(0,i);
                i--;
            }
        }
        return res;
    }
};

改了一下内存还超了

class Solution {
public:
    string minRemoveToMakevalid(string s) {
        string res = "";
        stack left;
        int n = s.length();
        int shift = 0;
        for(int i = 0; i < n; i++){
            if(s[i] == '('){
                left.push(i);
                shift++;
            }
            else if(s[i] == ')'){
                if(!left.empty()){
                    int index = left.top();
                    left.pop();
                    res = res.substr(0,index-shift+1) + '(' + res.substr(index-shift+1);
                    shift--;
                    res += ')';
                }
                else
                    shift++;
            }
            else
                res += s[i];
        }
        return res;
    }
};

又改了，还是很慢

class Solution {
public:
    string minRemoveToMakevalid(string s) {
        stack left;
        int n = s.length();
        vector redun;
        for(int i = 0; i < n; i++){
            if(s[i] == '('){
                left.push(i);
            }
            else if(s[i] == ')'){
                if(!left.empty()){
                    int index = left.top();
                    left.pop();
                }
                else
                    redun.push_back(i);
            }
        }
        while(!left.empty()){
            redun.push_back(left.top());
            left.pop();
        }
        sort(redun.begin(), redun.end());
        int shift = 0;
        for(int i = 0; i < redun.size(); i++){
            s = s.substr(0,redun[i]-shift) + s.substr(redun[i]-shift+1);
            shift++;
        }
        return s;
    }
};

还是一样慢我人傻了

class Solution {
public:
    string minRemoveToMakevalid(string s) {
        int balance = 0;
        int shift = 0;
        for(int i = 0; i < s.length(); i++){
            if(s[i] == '('){
                balance++;
            }
            else if(s[i] == ')'){
                if(balance){
                    balance--;
                }
                else{
                    s = s.substr(0,i) + s.substr(i+1);
                    i--;
                }
            }
        }
        reverse(s.begin(), s.end());
        balance = 0;
        for(int i = 0; i < s.length(); i++){
            if(s[i] == ')'){
                balance++;
            }
            else if(s[i] == '('){
                if(balance){
                    balance--;
                }
                else{
                    s = s.substr(0,i) + s.substr(i+1);
                    i--;
                }
            }
        }
        reverse(s.begin(), s.end());
        return s;
    }
};

最终简化，一样很慢，不明白c++其他人都咋做那么快

class Solution {
public:
    string minRemoveToMakevalid(string s) {
        int balance = 0;
        int shift = 0;
        for(int i = 0; i < s.length(); i++){
            if(s[i] == '('){
                balance++;
            }
            else if(s[i] == ')'){
                if(balance){
                    balance--;
                }
                else{
                    s = s.substr(0,i) + s.substr(i+1);
                    i--;
                }
            }
        }
        reverse(s.begin(), s.end());
        for(int i = 0; i < s.length(); i++){
            if(s[i] == '('){
                if(balance){
                    s = s.substr(0,i) + s.substr(i+1);
                    i--;
                    balance--;
                }
            }
        }
        reverse(s.begin(), s.end());
        return s;
    }
};