✅ C++ || 2 Appraches || Explained With Algorithm || Easy & Simple
1249. Minimum Remove to Make Valid Parentheses\nKNOCKCAT\n\n1. Easy C++\n2. Line by Line Explanation with Comments.\n3. Detailed Explanation \u2705\n4. 2 Apprao
# 1249. Minimum Remove to Make Valid Parentheses\n**KNOCKCAT**\n```\n1. Easy C++\n2. Line by Line Explanation with Comments.\n3. Detailed Explanation \u2705\n4. 2 Appraoches with initution.\n5. Please Upvote if it helps\u2B06\uFE0F\n6. Link to my Github Profile contains a repository of Leetcode with all my Solutions. \u2B07\uFE0F\n\t// \uD83D\uDE09If you Like the repository don\'t foget to star & fork the repository\uD83D\uDE09\n```\n[LeetCode](http://github.com/knockcat/Leetcode) **LINK TO LEETCODE REPOSITORY**\n\nPlease upvote my comment so that i get to win the 2022 giveaway and motivate to make such discussion post.\n**Happy new Year 2023 to all of you**\n**keep solving keep improving**\nLink To comment\n[Leetcode Give away comment](https://leetcode.com/discuss/general-discussion/2946993/2022-Annual-Badge-and-the-Giveaway/1734919)\n\n``` ```\n**APPROACH 1     O(n) & O(1)**\n\n* **ALGORITHM**\n* **Iterating the string from beginning.**\n\t* **take a cnt variable**, and **increase the cnt when you find an open parenthesis \'(\'.**\n\t* when you **find a close parenthiesis**, **2 cases were checked.**\n\t* i**f cnt is 0** , that **means no open parenthesis has occured earlier**.\n\t* therefore **replace the string index with \'#\'.**\n\t* **otherwise decrease the cnt**, as a **valid pair has found**.\n\t\n* Now **iterate the string from behind** and **repeat the same steps** , but **this time check for closing parenthisis**.\n\t* if **closing parenthesis occur increase the cnt**.\n\t* if **open parenthesis occur**, now **again 2 cases are need to check.**\n\t* if the **cnt == 0, that means no closing parenthisis occur** before **therfore replace that string index with \'#\'.**\n\t* Otherwise **decrease the cnt.**\n* **At end make the resultant string by excluding \'#\'**\n* **Time Complexity** is O(n+n+n) = **O(n)**  for each 3 steps\n* **Space Complexity** is **O(1)** , No extra space taken excluding result string.\n```\n```\n\n**CODE WITH EXPLANATION**\n```\n\t\t\t\t\t// \uD83D\uDE09\uD83D\uDE09\uD83D\uDE09\uD83D\uDE09Please upvote if it helps \uD83D\uDE09\uD83D\uDE09\uD83D\uDE09\uD83D\uDE09\nclass Solution\n{\npublic:\n    string minRemoveToMakeValid(string s)\n    {\n        int n = s.length();\n        string res = "";\n\n        int cnt = 0;\n        // iterating from beginnning\n        for (int i = 0; i < s.length(); ++i)\n        {\n            // if we find and open parenthesis increase the cnt\n            if (s[i] == \'(\')\n                ++cnt;\n            // if we found an close parenthisis\n            // check if cnt == 0 , that means we have no earlier open parenthesis,\n            // therefore replace that index by \'#\'\n            else if (s[i] == \')\')\n            {\n                if (cnt == 0)\n                    s[i] = \'#\';\n                // else decrease the cnt beacuse a valid pair is found\n                else\n                    --cnt;\n            }\n        }\n\n        cnt = 0;\n        // iterating from the end\n        for (int i = n - 1; i >= 0; --i)\n        {\n            // if we find and close parenthesis increase the cnt\n            if (s[i] == \')\')\n                ++cnt;\n            // if we found an open parenthisis\n            // check if cnt == 0 , that means we have no earlier close parenthesis,\n            // therefore replace that index by \'#\'\n            else if (s[i] == \'(\')\n            {\n                if (cnt == 0)\n                    s[i] = \'#\';\n                // else decrease the cnt beacuse a valid pair is found\n                else\n                    --cnt;\n            }\n        }\n\n        // making the resultant string by excluding \'#\'\n        for (int i = 0; i < s.length(); ++i)\n        {\n            if (s[i] != \'#\')\n                res.push_back(s[i]);\n        }\n\n        return res;\n    }\n};\n```\n\n**APPROACH 2 USING STACK**\n\n* **ALGORITHM**\n``` ```\n* **Using Stack** for **checking valadity of parenthesis**.\n* first it**erate the string** and when you **find a open parenthesis push it into the stack**.\n* if You **find and close parenthesis** , then **check if the stack is not empty**, if **stack is not empt**y that m**eans open parenthesis exist** **therefore pop the open parenthesis from the stack.**\n* **if the stack is empty** that **means no open parenthesis exist first** therefore **replace that string index with \'#\'.**\n* Now  there **may be a  case that string contain only open parenthesis** that is also an **invalid parenthesis.**\n* therefore **while stack doesn\'t become empty** **marked the indexes from the stack top with \'#\'.**\n* **pop that parenthesis from the stack.**\n* Now **at end** **create the resultant string excluding \'#\'**\n* **Time Complexity** is = **O(n)** \n* **Space Complexity** is **O(n)** , stack used.\n```\n```\n\n**CODE WITH EXPLANATION**\n\n```\n\t\t\t\t\t\t// \uD83D\uDE09\uD83D\uDE09\uD83D\uDE09\uD83D\uDE09Please upvote if it helps \uD83D\uDE09\uD83D\uDE09\uD83D\uDE09\uD83D\uDE09\nclass Solution\n{\npublic:\n    string minRemoveToMakeValid(string s)\n    {\n        stack<int> st;\n        string res = "";\n\n        for (int i = 0; i < s.length(); ++i)\n        {\n            // if we find open parenthesis push it to stack\n            if (s[i] == \'(\')\n                st.push(i);\n            // if we find close parenthisis check\n            // if there is a open parenthisis or the stack is empty\n            else if (s[i] == \')\')\n            {\n                // if stack  is empty then we need to remove that index from string\n                // replacing it with \'#\' for our convenience\n                if (st.empty())\n                    s[i] = \'#\';\n                else\n                    // if there is an open parenthesis than remove that  from the stack\n                    st.pop();\n            }\n        }\n\n        // now , if stack is not empty that means it has open parenthesis\n        // which have no closing parenthesis.\n        // so we have to replace that index of string with \'#\' for our convenience\n        while (!st.empty())\n        {\n            s[st.top()] = \'#\';\n            st.pop();\n        }\n\n        // making the resultant string by excluding \'#\'\n        for (int i = 0; i < s.length(); ++i)\n        {\n            if (s[i] != \'#\')\n                res.push_back(s[i]);\n        }\n\n        return res;\n    }\n};\n```
['Stack', 'C', 'C++']