0ms | Beginner Friendly C++ Sol with EXPLANATION
Intuition\nConsider test case \'()))((\'. For sure we need a stack to solve this problem. If you just do a simple dry run for this test case, you\'ll get to kno
# Intuition\nConsider test case \'**()))((**\'. For sure we need a stack to solve this problem. If you just do a simple dry run for this test case, you\'ll get to know the problem easily. For each opening bracket, we need a corresponding closing bracket. Basically we need to maintain only opening brackests in the stack.\n\n# Approach\n1. \'(\' push onto the stack.\n2. \')\' pop from the stack iff the stack is not empty.\n3. For step 2, if the incoming operator is a closing bracket and the stack is empty, we can conclude that there is not matching \'(\' that exists in the stack (as we are only maintaining \'(\' in the stack).\nso we do a cnt++\n4. **At last(one more case), if the stack contains only \'(\' brackets at last and the string exhausts, we can for sure conclude that no matching \')\' brackets were found.**\n5. Therefore while returning, we return the **sum of cnt and the size of the stack.**\n\n# Complexity\n- Time complexity:\nTraversal: O(N)\nPush, Pop: O(1)\n**Final: O(N)**\n\n- Space complexity:\nSC: O(N) \nif the string contains all the opening parenthesis\n\n# Code\n```\nclass Solution {\npublic:\n    int minAddToMakeValid(string s) {\n        stack<char> st;\n        int cnt = 0;\n        for(char ch : s) {\n            if(ch == \'(\') {\n                st.push(ch);\n            } \n            else if(ch == \')\') {\n                if(st.empty()) {\n                    cnt++;\n                } \n                else {\n                    st.pop(); \n                }\n            }\n        }\n        return cnt + st.size();\n    }\n};\n\n```
['Stack', 'C++']