C➕➕ Solution with explanation || T.C. -> O(n) & S.C -> O(n) || Stack
Intuition\nJust guessing which bracket is wrongly placed makes the problem more difficult as it can be anywhere.\n\nSo basic intuition could be, finding the wro
# Intuition\nJust guessing which bracket is wrongly placed makes the problem more difficult as it can be anywhere.\n\nSo basic intuition could be, finding the wrong bracket\'s or we can say unwanted bracket\'s indices in the string.\n\n# Approach\nApproach is very similar to that of finding valid parenthesis.\n\nSuppose we have ( ( ) ( ( ) ) ) ) ) (.\n\nNow lets try to find valid parenthesis using stack : - \n- ( - pushed , idx = 0\n- ( - pushed , idx = 1\n- ) - valid match as top of stack \'(\' ,so popped last \'(\', idx = 2\n\nwe can continue this way and at the end we would be having only unwanded bracket.\n\n\nIf you find a pair, that is valid one else it is invalid.\n\n# Complexity\n- Time complexity:\n    O(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    string minRemoveToMakeValid(string s) {\n    \n        stack<pair<char,int>> st;\n\n        for(int i = 0 ; i  < s.length() ; i++){\n            if(s[i]==\'(\'){\n                st.push({s[i],i});\n            }else if(s[i]==\')\'){\n                if(!st.empty() && st.top().first==\'(\')st.pop();\n                else st.push({s[i],i});\n            }\n        }\n\n        string str = "";\n\n        for(int i = s.length()-1; i>=0 ; i--){\n            if(!st.empty() && st.top().second == i){\n                st.pop();\n                continue;\n            }else str+=s[i];\n            \n        }\n\n        reverse(str.begin(),str.end());\n        return str;\n    }\n};\n```
['C++']