Beats 100% || O(1) space || C++ || Greedy
Intuition\n Describe your first thoughts on how to solve this problem. \nWhen dealing with valid parentheses, every opening parenthesis ( must have a correspond
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWhen dealing with valid parentheses, every opening parenthesis ( must have a corresponding closing parenthesis ). Our task is to count how many parentheses need to be added to make the string valid. This boils down to counting unmatched opening or closing parentheses as we traverse the string.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe traverse the string from left to right, keeping track of two counters:\n\n1.\topen: Counts unmatched opening parentheses (.\n2.\tclose: Counts unmatched closing parentheses ).\n\nFor each character in the string:\n\n\u2022\tIf it\u2019s an opening parenthesis (, we increment the open counter.\n\u2022\tIf it\u2019s a closing parenthesis ), we first check if there are any unmatched opening parentheses (open > 0). If there are, we pair the closing parenthesis with an unmatched opening parenthesis (decrement open). If not, we increment the close counter since this closing parenthesis is unmatched.\n\nAt the end, the total number of parentheses to add is the sum of unmatched opening parentheses (open) and unmatched closing parentheses (close).\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minAddToMakeValid(string s) {\n        int open = 0, close = 0;\n        for(auto it: s){\n            if(it == \'(\') ++open;\n            else{\n                if(open > 0) --open;\n                else ++close;\n            }\n        }\n        return open + close;\n    }\n};\nauto speedup = [](){ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0;}();\n```
['String', 'Greedy', 'C++']