1349

submission.cc

class Solution {
public:
    
    bool isLetter(char c) {
        return c >= 'a' && c <= 'z';
    }
    string minRemoveToMakeValid(string s) {
        stack<pair<char, int>> sta; 
        string ans = "";
        string buffer;
        int left = 0;
        for (int i = 0; i < s.length(); i++) {
             if (s[i] == '(') {
                 sta.push({'(', i});
             } else if (s[i] == ')') {
                 
                 if (!sta.empty() && sta.top().first == '(') {// the top of stack is '(', we find a valid pair.
                     sta.pop();
                 } else sta.push({')', i});
             }  
        }
        
        for (int i = s.length() - 1; i >= 0; i--) {
            if (!sta.empty() && sta.top().second == i) {// we should remove this char
                sta.pop();    
                continue; 
            }
            ans = s[i] + ans;
            
        }
        
        return ans;
        
    }
};