C++ | 2 Approaches | O(n), Beats 100% | No Extra Space (Best) | Explanation
APPROACH 1\nHere, we will use a stack for checking the validity of parentheses, and later remove the indexes of invalid parentheses from the string s. Thanks @h
**APPROACH 1**\nHere, we will use a **stack** for checking the validity of parentheses, and later remove the indexes of invalid parentheses from the string `s`. Thanks [@harmxnkhurana](https://leetcode.com/harmxnkhurana) for the suggestion of directly marking the invalid parentheses in string `s` rather than redundant storing it in a different vector. \n- First, iterate the string `s` and mark the index of those characters which need to be removed to make it *parentheses string* using a special symbol **`\'#\'`**.\n- Here, a **stack** is used for finding the **valid** pair of parentheses, and while doing so also **mark** the indexes of **invalid parentheses** in ```s```.\n- Finally, iterate `s` again and append **non-marked symbol** (`#`) to `ans`.\n\n**COMPLETE CODE**\n```\nclass Solution {\npublic:\n    string minRemoveToMakeValid(string s) {\n        \n        stack<int>st; // helper stack for finding matching parentheses\n        \n        for(int i=0;i<s.length();++i){\n            if(s[i]==\'(\'){ // for open parentheses push into stack\n                st.push(i);\n            }\n            else if(s[i]==\')\'){ // for closing parentheses\n                // if no matching previous open parentheses found, we need to remove the index of that open parentheses from "s" so for now we are marking it with special character \'#\'\n                if(st.empty()){ \n                    s[i]=\'#\';\n                }\n                else{\n                    // if matching open parentheses found remove that from the stack\n                    st.pop();\n                }\n            }\n        }\n\n        // if stack is not empty, that means it contains open parentheses indexes which don\'t have any matching closing parentheses\n        while(!st.empty()){\n            s[st.top()]=\'#\';\n            st.pop();\n        }\n        \n        string ans="";\n        for(int i=0;i<s.length();++i){\n            if(s[i]!=\'#\'){ // append not marked character to the end of "ans"\n                ans.push_back(s[i]);\n            }\n        }\n        \n        return ans;\n    }\n};\n```\n\n**TIME COMPLEXITY**\n**O(n)**\n\n**SPACE COMPLEXITY**\n**O(n)** [ *For stack* ]\n\n---\n\n**APPROACH 2 ( Better Approach )**\nIn this approach, we don\'t need a stack so **no extra space** will be used. Thanks [@Ajna2](https://leetcode.com/Ajna2) for the suggestion of keeping a count variable instead of using a stack.\n- First, create a `count` variable for storing the number of **opening** or **closing** brackets as per our need.\n- **STEP 1:**\n\t- Initialize `count=0`. For this step, we will use `count` for storing the number of **open** brackets.\n\t- Then, iterate the string `s` from **start** and at each iteration:\n\t\t- if **open bracket** found, then **increase** `count`.\n\t\t- if **close bracket** found, then check *if* **no. of close brackets > no. of open brackets**, then mark that character in `s` by *replacing* it by **`#`**, *else* **decrease** the `count` ( as **matching parentheses** found ).\n\t```\n\tint count=0; \n\tfor(int i=0;i<n;++i){\n\t\tif(s[i]==\'(\'){ // for open bracket\n\t\t\t++count;\n\t\t}\n\t\telse if(s[i]==\')\'){ // for close bracket\n\t\t\tif(count==0){  // if no. of close brackets > no. of open brackets\n\t\t\t\ts[i]=\'#\';\n\t\t\t}\n\t\t\telse{\n\t\t\t\t// if matching parentheses found decrease count\n\t\t\t\t--count;\n\t\t\t}\n\t\t}\n\t}\n\t```\n- **STEP 2  ( Reverse of STEP 1 )**\n\t- Again, make `count=0`. For this step, we will use `count` for storing the number of **close** brackets.\n\t- Then, iterate the string `s` from the **end** and at each iteration:\n\t\t- if **close bracket** found, then **increase** `count`.\n\t\t- if **open bracket** found, then check *if* **no. of open brackets > no. of close brackets**, then mark that character in `s` by *replacing* it by **`#`**, *else* **decrease** the `count` ( as **matching parentheses** found ). \n\t```\n\tcount=0;\n\tfor(int i=n-1;i>=0;--i){\n\t\tif(s[i]==\')\'){ // for close bracket\n\t\t\t++count;\n\t\t}\n\t\telse if(s[i]==\'(\'){ // for open bracket\n\t\t\tif(count==0){ // if no. of open brackets > no. of close brackets\n\t\t\t\ts[i]=\'#\';\n\t\t\t}\n\t\t\telse{\n\t\t\t\t// if matching parentheses found decrease count\n\t\t\t\t--count;\n\t\t\t}\n\t\t}\n\t}\n\t```\n- **STEP 3:**\n\t- Iterate the string `s` and append each non - marked character (`#`) to `ans` string.\n\t- return `ans`.\n\t```\n\tstring ans="";\n\tfor(int i=0;i<n;++i){\n\t\tif(s[i]!=\'#\'){ \n\t\t\tans.push_back(s[i]);\n\t\t}\n\t}\n\treturn ans;\n\t```\n\n**COMPLETE CODE**\n```\nclass Solution {\npublic:\n    string minRemoveToMakeValid(string s) {\n        int n=s.length();\n        // Step 1 : Iterate from start\n        int count=0; \n        for(int i=0;i<n;++i){\n            if(s[i]==\'(\'){ // for open bracket\n                ++count;\n            }\n            else if(s[i]==\')\'){ // for close bracket\n                if(count==0){  // if no. of close brackets > no. of open brackets\n                    s[i]=\'#\';\n                }\n                else{\n                    // if matching parentheses found decrease count\n                    --count;\n                }\n            }\n        }\n        \n        // Step 2 : Iterate from end\n        count=0;\n        for(int i=n-1;i>=0;--i){\n            if(s[i]==\')\'){ // for close bracket\n                ++count;\n            }\n            else if(s[i]==\'(\'){ // for open bracket\n                if(count==0){ // if no. of open brackets > no. of close brackets\n                    s[i]=\'#\';\n                }\n                else{\n                    // if matching parentheses found decrease count\n                    --count;\n                }\n            }\n        }\n        \n        // Step 3 : Create "ans" by ignoring the special characters \'#\'\n        string ans="";\n        for(int i=0;i<n;++i){\n            if(s[i]!=\'#\'){ \n                ans.push_back(s[i]);\n            }\n        }\n        return ans;\n    }\n};\n```\n\n**TIME COMPLEXITY**\n**O(n+n+n) = O(n)** [ *Each step takes O(n) time* ]\n\n**SPACE COMPLEXITY**\n**O(1)** [ *No extra space used, ignoring "ans"* ]
['Stack', 'C']