🧠[C++/Java/Python]: One Pass Easy Solution
Approach\n> 1. Initialize an empty stack st to keep track of unmatched opening parentheses.\n> 2. Iterate through each character i in the input string s.\n\n> 3
## Approach\n> 1. Initialize an empty stack st to keep track of unmatched opening parentheses.\n> 2. Iterate through each character i in the input string s.\n\n> 3. For each character i:\n> * If the stack is empty, push the character onto the stack because there\'s nothing to match it with.\n> * If the stack is not empty and the current character i is a closing parenthesis \')\' and the top of the stack contains an opening parenthesis \'(\', then pop the opening parenthesis from the stack because a valid pair has been found.\n> * If none of the above conditions are met, push the current character i onto the stack.\n> 4. After processing all characters in the string, the remaining unmatched opening parentheses (if any) will be left on the stack. The size of the stack represents the minimum number of additions needed to make the string valid.\n> 5. Return the size of the stack as the result, which is the minimum number of additions required to make the string valid.\n\n---\n\n\n\n## Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ --> \n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n---\n\n\n\n## Code\n```C++ []\nclass Solution {\npublic:\n    int minAddToMakeValid(string s) {\n        stack<char> st;\n\n        for(auto i: s){\n            if(st.empty())\n                st.push(i);\n            else if(st.top() == \'(\' and i == \')\')\n                st.pop();\n            else\n                st.push(i);\n        }\n        return st.size();\n    }\n};\n```\n```Java []\nclass Solution {\n    public int minAddToMakeValid(String s) {\n        Stack<Character> stack = new Stack<>();\n\n        for (char c : s.toCharArray()) {\n            if (stack.isEmpty()) {\n                stack.push(c);\n            } else if (stack.peek() == \'(\' && c == \')\') {\n                stack.pop();\n            } else {\n                stack.push(c);\n            }\n        }\n\n        // At this point, the stack contains unmatched parentheses.\n        // The size of the stack is the minimum number of additions required.\n        return stack.size();\n    }\n};\n```\n```Python []\nclass Solution:\n    def minAddToMakeValid(self, s: str) -> int:\n        stack = []\n\n        for char in s:\n            if not stack:\n                stack.append(char)\n            elif stack[-1] == \'(\' and char == \')\':\n                stack.pop()\n            else:\n                stack.append(char)\n\n        # At this point, the stack contains unmatched parentheses.\n        # The length of the stack is the minimum number of additions required.\n        return len(stack)\n\n```\n\n---\n\n\n![cat.webp](https://assets.leetcode.com/users/images/38d75ce7-39ff-479e-b239-5709c2390ea7_1693674627.9358778.webp)\n
['Python', 'C++', 'Java', 'Python3']