Buidling_Intuition_step_by_step | Comments | Stack_Based | c++ | proper_Intuition
take the first taste case:  "lee(t(c)o)de)"\n  answer should be : "lee(t(c)o)de"\n  \n  intuition: \n    1) if we observe, the one who opens later need to close
take the first taste case:  "lee(t(c)o)de)"\n  answer should be : "lee(t(c)o)de"\n  \n  intuition: \n    1) if we observe, the one who opens later need to closed first so stack comes into picture \n    2) so here \'(\' at index 5 needs to closed first and then \'(\' at index 3 needs to closed subsequently\n    3) simalarly we maintain the count for open_brackets and closed_brackets \n    4) if (count of closed brackets becomes) > (the open_brackets) that means we don\'t have any open bracket before this closed bracket so we need to eleminate this closed bracket from answer string\n    \n\tso here in this first tast case \n\t1)closed bracket at index 7 will be satisfy with open bracket at index 5\n\t2)closed bracket at index 9 will be satisfy with open bracket at index 3\n\t3)but closed bracket at index 12 does not have any open bracket so we will not take that one in our answer\n\t\nNow take second test case: "a)b(c)d"\nanswer should be : "ab(c)d"\n```\nso here in second test case:\n \n 1)here closed bracket at index 1 does not have any open bracket before it so we will not take that in         our answer\n 2)but closed bracket at index 5 have open brakcet before it to satisfy so we will take it\n```\n\nNow take 3rd test case : "))(("\nanswer: ""\n\n```\nSo here int 3rd test case:\n1)here closed brackets at index 0 and 1 are out from our answer\n2)but open brackets at index 2 and 3 does not have any closed brackets to satisfy them so no need to      take them in answer \n```\n\n\n```\nso Approach:\n1. we will create empty stack\n2. then tarverse the string from left to right\n    1. if s[i]!=\'(\' && s[i]!=\')\' then add it into our stack\n    2. else if  s[i]==\'(\' then add into stack and increase the count of open_brackets++\n    3. else means closed bracket add it to stack increase the count of closed_brackets but \n         1. if closed_brackets>open_brackets then remove the closed bracket from the stack and \n                       decrese the count of closed bracket\n3.so uptil now we have taken care of closed brackets but how to takel open brackets\n4. so we have count of open_brackets and closed_brackets\n5. if open_brackets are more then closed_brackets means their are more (open_brackets - closed_brackest) open brackets so to handle them we will remove first (open_bracket - closed_brackets) open brackest from stack \n```\n     \n  \n\nThanks and if you liked please upvote\n\n```\nstring minRemoveToMakeValid(string s) {\n        \n        int length_s=s.size();     //getting the length of string \n        stack<char> stk;           //creating the empty stack for storing the characters\n        \n        int open_brackets=0;       //initizing the count for open_brackets\n        int close_brackets=0;      ////initizing the count for close_brackets\n        \n        for(int i=0;i<length_s;i++) //traversing the string from left to right\n        {\n            if(s[i]!=\'(\' && s[i]!=\')\')  // if it character not equal to open and closed bracket \n            {\n                stk.push(s[i]);          //then add it to stack\n            }\n            else\n            {\n                if(s[i]==\'(\')          //if it is open bracket\n                {\n                    open_brackets++;   //increase the count of open_bracket\n                    stk.push(s[i]);    //add it to stack \n                }\n                else\n                {\n                    close_brackets++;  //if it is closed bracket\n                    stk.push(s[i]);    //add it to satck \n                    if(close_brackets>open_brackets) //if closed brackets are more than open brackets then \n                    {\n                        stk.pop();                   //pop the closed bracket which we have added\n                        close_brackets--;            //and decrease the count og close_bracket\n                    }\n                }\n            }\n        }\n        string ans="";                               //initilizing the answer string\n        if(open_brackets>close_brackets)             //we have already taken care of closed brackets now need  to handle open brackets\n        {\n            int diff=open_brackets-close_brackets;  //number of open brackets more than closed brackets need to remove from answer string\n            while(stk.empty()==false)\n            {\n                char top=stk.top();\n                stk.pop();\n                \n                if(top==\'(\' && diff!=0)       \n                {\n                    diff--;\n                }\n                else\n                {\n                    ans+=top;\n                }\n            }\n        }\n        else\n        {\n            while(stk.empty()==false)\n            {\n                char top=stk.top();\n                stk.pop();\n                ans+=top;\n            }\n        }\n        reverse(ans.begin(),ans.end());                //reversing the string \n        return(ans);\n    }\n```\n
['Stack', 'C']