Min remove to make valid parantheses | C++ | Stack | Code explained
\nclass Solution {\npublic:\n    string minRemoveToMakeValid(string s) {\n\t\n\t\t// define a stack which holds the parantheses along with the position\n       
```\nclass Solution {\npublic:\n    string minRemoveToMakeValid(string s) {\n\t\n\t\t// define a stack which holds the parantheses along with the position\n        stack<pair<int, char> > stk;\n\t\t\n        for(int i=0; i<s.length(); i++){\n            if(s[i] == \'(\'){\n\t\t\t    // if opening braces, push into the stack\n                stk.push(make_pair(i, \'(\'));\n            }else if(s[i] == \')\'){\n\t\t\t    // If closing braces, check if opening present or not. If yes, pop it.\n\t\t\t\t// Else mark that position of closing brace with \'1\' in the string.\n\t\t\t\t// 1 suggest that it should get removed.\n                if(stk.empty()){\n                    s[i] = \'1\';\n                }else{\n                    stk.pop();\n                }\n            }\n        }\n        \n\t\t// Now check for any leftover opening braces in the stack.\n\t\t// Mark those position with \'1\'.\n\t\t// That is they should get removed.\n        while(!stk.empty()){\n            pair<int, char> TOP = stk.top();\n            s[TOP.first] = \'1\';\n            stk.pop();\n        }\n        \n\t\t\n\t\t// Now push all the characters in a string which aren\'t marked as \'1\'.\n\t\tstring output = "";\n        for(int i=0; i<s.length(); i++){\n            if(s[i] != \'1\'){\n                output.push_back(s[i]);\n            }\n        }\n        \n        return output;\n    }\n};\n```\n\nWhy am using 1 to mark position?\nCause it is previously said to us that input string will only contain \'(\' and \')\' and lower-case letters.\n\nPlease *upvote* if you like the solution.
[]