1249. Minimum Remove to Make Valid Parentheses

Given a string s of ‘(‘ , ‘)’ and lowercase English characters.

Your task is to remove the minimum number of parentheses ( ‘(‘ or ‘)’, in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

• It is the empty string, contains only lowercase characters, or
• It can be written as AB (A concatenated with B), where A and B are valid strings, or
• It can be written as (A), where A is a valid string.

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        list<int> l;
        for(int i = 0; i < s.length(); i++) {
            switch (s[i]) {
                case '(' : l.push_back(i); break;
                case ')' : if(!l.empty()) l.pop_back(); else s[i] = '*'; break;
            }
        }
        for(auto& pos : l) s[pos] = '*';
        stringstream ss;
        for(auto& c : s)
            if(c != '*')
                ss << c;
        return ss.str();
    }
};