Detailed C++ solution with Stack and without Stack | Easy to Understand |
Solution Without stack\niterative soultion ----->\n==> if whenever the string is not valid we replace it with (*) so that we do not add that character to out re
**Solution Without stack**\n**iterative soultion ----->\n==> if whenever the string is not valid we replace it with (*) so that we do not add that character to out result.\n==> we do the above operation from left side and than right side and finally return the string.\n```\nclass Solution {\npublic:\n    string minRemoveToMakeValid(string s) {\n        int cnt = 0;\n        // starting from left to right \n        // check if string is valid or not\n        // if not valid replace * with string\n        for(int i=0; i<s.size(); i++) {\n            if(s[i] == \'(\') cnt++;\n            else if(s[i] == \')\') {\n                cnt--;\n                if(cnt < 0) {\n                    s[i] = \'*\';\n                    cnt = 0;\n                }\n            }\n        }\n        \n        cnt =  0;\n        // starting from right to left\n        for(int i=s.size()-1; i>=0; i--) {\n            if(s[i] == \')\') cnt++;\n            else if(s[i] == \'(\') {\n                cnt--;\n                if(cnt < 0) {\n                    s[i] = \'*\';\n                    cnt = 0;\n                }\n            }\n        }\n        string ans = "";\n        for(int i=0; i<s.size(); i++) {\n            if(s[i] != \'*\') ans += s[i];\n        }\n        return ans;\n    }\n};\n```\n**Solution With Stack**\n==>Push \'(\' into a stack and whenever \')\' appears in the string, try to pop \'(\' from stackif exists.\n==> If \'(\' does not exist, then erase \')\' from string.\n==> After parsing the entire string, erase extra \'(\' present in stack from string.\n```\nclass Solution {\npublic:\n    string minRemoveToMakeValid(string s) {\n        stack<int> box;\n        int n = s.size();\n        \n        for(int i=0; i<n; i++) {\n            if(s[i] == \')\'){\n                if(!box.empty() && s[box.top()] == \'(\'){\n                    box.pop();\n                }else{\n                    s.erase(i,1);\n                    i--;\n                }\n            }\n            else if(s[i] == \'(\'){\n                box.push(i);\n            }\n        }\n        \n        while(!box.empty()) {\n            s.erase(box.top(),1);\n            box.pop();\n        }\n        \n        return s;\n    }\n};\n```\n\nupvote if u like
['Stack', 'C', 'Iterator', 'C++']