1249 | C++ | Easy O(N) solution with explanation
Please upvote if you find this solution helpful :)\n\nAlgorithm:\n initialize count = 0 and result string\n\nStart traversing from beginning\n if we find open p
**Please upvote if you find this solution helpful :)**\n\n**Algorithm:**\n* initialize count = 0 and result string\n\n**Start traversing from beginning**\n* if we find open parenthesis then we increase the count by 1 that helps in find valid pair.\n* if we find close parenthesis there may be 2 cases.\n* \tif count==0 it means there is no open parenthesis and this close parenthesis is invalid so we replace s[i] with \'_\'.\n* \telse decrease the count by 1 because we find one valid pair.\n\nNow, again initialze count = 0\n\n**and start traversing from the end.**\n* \tif we find close parenthesis then we increase the count by 1that helps in find valid pair.\n* \tif we find open parenthesis there may be 2 cases.\n* \tif count==0 it means this open parenthesis is invalid so we replace s[i] with \'_\'.\n* \telse decrease the count by 1 becuase we find valid pair.\n\t\t\n\t\t\n**Now, we again traverse through string from beginning and if s[i] != \'_ \' we put that char into the result string.**\n\n**Time Complexity - O(N)\nSpace Complexity - O(1).**\n\n```\nclass Solution {\npublic:\n    string minRemoveToMakeValid(string s) \n    {\n        string res = "";\n        int n = s.size(), count = 0;\n        \n        //iterate from beginning\n        for(int i=0; i<n; i++)\n        {\n            //if get \'(\' increase count by 1\n            if(s[i] == \'(\')\n                count++;\n            \n            else if(s[i] == \')\')\n            {\n                // if count=0 replace \')\' with \'_\'\n                if(count==0)\n                    s[i] = \'_\';\n                \n                else \n                    count--;\n            }\n        }\n        \n        count = 0;\n        //Now iterate from end\n        for(int i=n-1; i>=0; i--)\n        {\n            //if get \')\' increase count by 1\n            if(s[i] == \')\')\n                count++;\n            \n            else if(s[i] == \'(\')\n            {\n                //if count=0 replace \'(\' with \'_\'\n                if(count==0)\n                    s[i] = \'_\';\n                else \n                    count--;\n            }\n        }\n        \n        //add all the char into res string except \'_\'\n        for(int i=0; i<n; i++)\n        {\n            if(s[i] != \'_\')\n            {\n                res.push_back(s[i]);\n            }\n        }\n        return res;\n    }\n};\n```\n\n\n**Please upvote if you find this solution helpful :)**
[]