💡 C++ | O(n) | Space O(n) [Stack] -> O(1) [No Stack]  | With Full Explanation ✏️
Intuition\nThe problem asks us to make a string of parentheses valid by adding the minimum number of parentheses. A valid string means every open parenthesis ( 
# Intuition\nThe problem asks us to make a string of parentheses valid by adding the minimum number of parentheses. A valid string means every open parenthesis `(` must have a corresponding close parenthesis `)`. The goal is to find how many parentheses need to be added to make the string valid.\n\nMy first thought is to use a stack or counters to keep track of unmatched parentheses as I iterate through the string.\n\n# Approach\nWe can use two approaches:\n\n1. **Using a Stack:**\n- Use a stack to store open parentheses `(`.\n- Traverse the string, and if we encounter a closing parenthesis `)` and the stack is not empty, we pop the open parenthesis from the stack (since it has a valid match).\n- If the stack is empty, we increment the answer because it means we have an unmatched closing parenthesis.\n- After traversing the string, the remaining unmatched open parentheses in the stack will need to be closed, so we add the size of the stack to our answer.\n2. **Space-Optimized Approach:**\n- Instead of using a stack, we can use a counter to keep track of open parentheses `(`.\n- Traverse the string, and for each open parenthesis, increment the counter. For each close parenthesis `)`, check if there is an unmatched open parenthesis to close. If yes, decrement the counter. If no, increment the answer (because it means we need an extra opening parenthesis).\n- After traversing the string, the counter will represent the number of unmatched open parentheses, which will need to be closed by adding the corresponding number of closing parentheses.\n\n# Complexity\n### Using a Stack :-\n- **Time complexity:** `O(n)` \u2014 We traverse the string once.\n- **Space complexity:** `O(n)` \u2014 In the worst case, all the parentheses are open, so the stack will store `n` elements.\n### Space-Optimized Approach :-\n- **Time complexity:** `O(n)` \u2014 We traverse the string once.\n- **Space complexity:** `O(1)` \u2014 Only two counters are used.\n\n# Code\n## Using a Stack\n```cpp []\nclass Solution {\npublic:\n    int minAddToMakeValid(string s) {\n        int ans = 0;\n        stack<char> s1; // stack to track unmatched open parentheses\n        for (int i = 0; s[i] != \'\\0\'; i++) {\n            if (s[i] == \'(\') {\n                s1.push(\'(\'); // push open parenthesis\n            } else {\n                if (!s1.empty() && s1.top() == \'(\') {\n                    s1.pop(); // valid match, pop from stack\n                } else {\n                    ans++; // no match, increment answer\n                }\n            }\n        }\n        return ans + s1.size(); // add remaining unmatched open parentheses\n    }\n};\n```\n## Space-Optimized Approach\n```cpp []\nclass Solution {\npublic:\n    int minAddToMakeValid(string s) {\n        int ans = 0;\n        int lopen = 0; // counter for unmatched open parentheses\n        \n        for (int i = 0; s[i] != \'\\0\'; i++) {\n            if (s[i] == \'(\') {\n                lopen++; // increment for open parenthesis\n            } else {\n                if (lopen != 0) {\n                    lopen--; // valid match, decrement counter\n                } else {\n                    ans++; // unmatched closing parenthesis\n                }\n            }\n        }\n        return ans + lopen; // add remaining unmatched open parentheses\n    }\n};\n```\n\n\n![anonupvote.jpeg](https://assets.leetcode.com/users/images/bf7ce48f-1a34-404c-8610-410d43112c2c_1720413559.1746094.jpeg)\n\n# Ask any doubt !!!\nReach out to me \uD83D\uDE0A\uD83D\uDC47\n\uD83D\uDD17 https://tushar-bhardwaj.vercel.app/
['String', 'Stack', 'Greedy', 'C++']