Counting Open and Closed Parentheses
Intuition\nThe task is to remove the minimum number of parentheses to make the string valid. The approach taken in this code is to traverse the string twice. In
# Intuition\nThe task is to remove the minimum number of parentheses to make the string valid. The approach taken in this code is to traverse the string twice. In the first loop, we count the opening parentheses encountered and maintain a valid string by appending characters accordingly. If a closing parenthesis is encountered and there are unmatched opening parentheses, we include it in the resulting string and decrement the count of unmatched opening parentheses. In the second loop, if there are still unmatched opening parentheses, we traverse the string backward to remove any extra opening parentheses.\n\n# Approach\n1. Initialize variables `open` and `close` to track the counts of opening and closing parentheses, respectively, and an empty string `ans` to store the resulting valid string.\n2. Iterate through the string:\n   - If the character is not a parenthesis, append it to `ans`.\n   - If the character is an opening parenthesis, increment the `open` count and append it to `ans`.\n   - If the character is a closing parenthesis and there are unmatched opening parentheses (`open > 0`), decrement the `open` count and append the closing parenthesis to `ans`.\n3. If there are still unmatched opening parentheses (`open > 0`), indicating extra opening parentheses, traverse the string backward to remove them:\n   - Iterate through the reversed string:\n     - If the character is not a parenthesis, append it to a new string.\n     - If the character is a closing parenthesis, increment the `close` count and append it to the new string.\n     - If the character is an opening parenthesis and there are unmatched closing parentheses (`close > 0`), decrement the `close` count and append the opening parenthesis to the new string.\n   - Reverse the new string to obtain the final valid string.\n4. Return the final valid string.\n\n# Complexity\n- Time complexity: $$O(n)$$\n- Space complexity: $$O(n)$$\n# without stack  \n```c++ []\nclass Solution {\npublic:\n    string minRemoveToMakeValid(string s) {\n        int open = 0, close = 0;\n        string ans;\n        //traverse from start to end to eleminate extra closing braces\n        for (const char& c : s) {\n            if (c != \'(\' && c != \')\') {\n                ans += c;\n            } else if (c == \'(\') {\n                open++;\n                ans += c;\n            } else if (open > 0) {\n                ans += c;\n                open--;\n            }\n        }\n\n       //traverse from end to start to remove extra opening braces\n        if (open > 0) {\n             int n = ans.length();\n            s = ans;\n            ans = "";\n            open = 0, close = 0;\n            for (int i = n - 1; i >= 0; i--) {\n                char c = s[i];\n                if (c != \'(\' && c != \')\') {\n                    ans += c;\n                } else if (c == \')\') {\n                    close++;\n                    ans += c;\n                } else if (close > 0) {\n                    ans += c;\n                    close--;\n                }\n            }\n        }\n        else{\n            return ans;\n        }\n        reverse(ans.begin(), ans.end());\n        return ans;\n    }\n};\n```\n# with stack\n```c++ []\nclass Solution {\npublic:\n    string minRemoveToMakeValid(string s) {\n        int open = 0, close = 0;\n        stack<char>st;\n        //traverse from start to end to eleminate extra closing braces\n        for (const char& c : s) {\n            if (c != \'(\' && c != \')\') {\n                st.push(c);\n            } else if (c == \'(\') {\n                open++;\n                st.push(c);\n            } else if (open > 0) {\n                st.push(c);\n                open--;\n            }\n        }\n        string ans;\n         //traverse from left to right to remove extra opening braces\n            open = 0, close = 0;\n            while(!st.empty()) {\n                char c = st.top();\n                st.pop();\n                if (c != \'(\' && c != \')\') {\n                    ans += c;\n                } else if (c == \')\') {\n                    close++;\n                    ans += c;\n                } else if (close > 0) {\n                    ans += c;\n                    close--;\n                }\n            }\n        \n        reverse(ans.begin(), ans.end());\n        return ans;\n    }\n};\n```
['C++']