🏗️ Two Approaches [SC: O(n) vs O(1)]: Stack vs. Greedy 🚀
Approach\n1. # First Approach:\n    We traverse the string, and for each character:\n    If it\'s an opening parenthesis (, we push it onto the stack.\n    If i
# Approach\n1. # First Approach:\n    We traverse the string, and for each character:\n    If it\'s an opening parenthesis (, we push it onto the stack.\n    If it\'s a closing parenthesis ), we check if the top of the stack is an opening parenthesis (. If so, we pop the stack (since they balance each other). Otherwise, we push the closing parenthesis ) onto the stack.\n    At the end, the size of the stack gives the number of unmatched parentheses.\n2. # Second Approach:\n    Instead of using a stack, we maintain two variables:\n    openingB counts unmatched opening parentheses (.\n    closingB counts unmatched closing parentheses ).\n    For each closing parenthesis ), we check if there is an unmatched opening parenthesis (. If so, we decrement the count of unmatched openings. If not, we increment the count of unmatched closings.\n    For each opening parenthesis (, we increment the openingB count.\n    The result is the sum of unmatched opening and closing parentheses.\n\n# Complexity\n1. # First Approach:\n- Time complexity:O(n), where n is the length of the string. We process each character once.\n\n- Space complexity:O(n), due to the stack storing unmatched parentheses in the worst case.\n\n2. # Second Approach:\n- Time complexity:O(n), where n is the length of the string. We process each character once.\n- Space complexity:O(1), as we only use two integer variables, regardless of the input size.\n\n\n# Code First Approach:\n```cpp []\nclass Solution {\npublic:\n    int minAddToMakeValid(string s) {\n        stack<char>st;\n        for(const char& ch : s){\n            bool isPoped = false;\n            if(!st.empty()){\n                char top = st.top();\n                if(ch==\')\' && top == \'(\'){\n                    st.pop();\n                    isPoped = true;\n                }\n            }\n            if(!isPoped){\n                st.push(ch);\n            }\n\n        }\n        return st.size();\n    }\n};\n```\n\n# Code Second Approach\n```cpp []\nclass Solution {\npublic:\n    int minAddToMakeValid(string s) {\n        int openingB = 0;\n        int closingB  = 0;\n        for(const char& ch : s){\n            if(ch == \')\'){\n                if(openingB >=1){\n                    openingB--;\n                }\n                else{\n                    closingB++;\n                }\n            }\n            else{\n                openingB++;\n            }\n        }\n        return openingB+closingB;\n    }\n};\n```\n![image.png](https://assets.leetcode.com/users/images/21478208-ccea-448b-b3b4-02574401edc0_1727318750.5181131.png)
['String', 'Stack', 'Greedy', 'C++']