💡| O(n) | C++ 0ms Beats 100.00% | Easy Solution🧠| Py3 23ms Beats 98.69% | Java 0ms Beats 100.00% |
\n#\n---\n\n> # Intuition\nTo determine the minimum number of insertions required to make the parentheses string valid, we need to track the number of unmatched
\n#\n---\n\n> # Intuition\nTo determine the minimum number of insertions required to make the parentheses string valid, we need to track the number of unmatched opening and closing parentheses. As we traverse the string, we increment counts based on whether the current character is an opening or closing parenthesis. When a closing parenthesis is found but no opening parenthesis is available to match, we increase the count of unmatched closing parentheses. At the end, the total unmatched parentheses are the result of adding unmatched opening and closing parentheses.\n\n> # Approach\nWe initialize two counters: one for unmatched opening parentheses and another for unmatched closing parentheses. As we traverse the string, we increment the opening counter when we find an opening parenthesis. When we find a closing parenthesis, if there are unmatched opening parentheses, we decrement the opening counter (indicating a match). Otherwise, we increment the closing counter (indicating an unmatched closing parenthesis). The result is the sum of unmatched opening and closing parentheses.\n\n> # Complexity\n- **Time Complexity** $$O(n)$$, where n is the length of the string. We process each character once.\n- **Space Complexity** $$O(1)$$, since we only use a few variables for tracking counts.\n\n---\n\n> # Code\n```cpp []\nclass Solution {\npublic:\n    int minAddToMakeValid(string s) {\n        int o{0}, c{0};\n        for (char ch : s) ch == \'(\' ? ++o : o ? --o : ++c;\n        return o + c;\n    }\n};\n```\n```Java []\nclass Solution {\n    public int minAddToMakeValid(String s) {\n        int o = 0, c = 0;\n        for (char ch : s.toCharArray()) {\n            if (ch == \'(\') {\n                o++;\n            } else if (o > 0) {\n                o--;\n            } else {\n                c++;\n            }\n        }\n        return o + c;\n    }\n}\n```\n```python3 []\nclass Solution:\n    def minAddToMakeValid(self, s: str) -> int:\n        o = c = 0\n        for ch in s:\n            if ch == \'(\':\n                o += 1\n            elif o > 0:\n                o -= 1\n            else:\n                c += 1\n        return o + c\n```\n\n---\n\n> **CPP**\n> ![image.png](https://assets.leetcode.com/users/images/7a42cf00-0afc-43aa-95f0-3c8f96432dcd_1728444165.6912827.png)\n> **Java**\n> ![image.png](https://assets.leetcode.com/users/images/495dbd74-1b8f-450c-ac06-514b4e25ee6c_1728444890.0970275.png)\n> **Python3**\n> ![image.png](https://assets.leetcode.com/users/images/672702f0-2289-4f76-84e8-dd369af3e200_1728444872.0458703.png)\n![Designer.png](https://assets.leetcode.com/users/images/5395952a-4267-4b87-b81f-f28780669704_1726803172.327018.png)\n\n---\n\n> ### Additional Notes\n> Note : The approach is highly efficient with a time complexity of $$\uD835\uDC42(\uD835\uDC5B)$$, making a single pass through the string, and constant space. This makes sure optimal performance for the given constraints.\n\n
['C++', 'Java', 'Python3']