PYTHON || OPTIMAL SOLUTION || 100% EFFICIENT || EASY TO UNDERSTAND ||
if it\'s help, please up \u2B06 vote! \u2764\uFE0F\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \n- The intuition behind this pro
# if it\'s help, please up \u2B06 vote! \u2764\uFE0F\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- The intuition behind this problem is to determine the minimum number of parentheses (opening or closing) that need to be added to a given string to make it a valid parentheses expression. A valid parentheses expression is one where all opening parentheses have a matching closing parenthesis, and all closing parentheses have a matching opening parenthesis.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Initialize two variables: count to keep track of the balance between opening and closing parentheses, and ans to store the minimum number of parentheses that need to be added.\nIterate through each character paran in the input string s:\n\n- If paran is an opening parenthesis \'(\', increment count by 1. \n- If paran is a closing parenthesis \')\', decrement count by 1.\n- If count becomes -1, it means we have encountered an extra closing parenthesis without a corresponding opening parenthesis. In this case, reset count to 0 and increment ans by 1 to account for the extra opening parenthesis that needs to be added.\n\n\n- After the loop finishes, add the final value of count to ans. The count variable represents the number of unmatched opening parentheses that need to be closed with closing parentheses.\n- Return ans, which represents the minimum number of parentheses that need to be added to make the string valid.\n\n# Complexity\n- Time complexity: O(n), where n is the length of the input string s. The code iterates through the string once.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1), since the solution uses a constant amount of extra space to store temporary variables.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution(object):\n    def minAddToMakeValid(self, s):\n        """\n        :type s: str\n        :rtype: int\n        """\n        count = ans = 0\n        for paran in s:\n            if paran == \'(\':\n                count += 1\n            else:\n                count -= 1\n                if count == -1:\n                    count = 0\n                    ans += 1\n        ans += count\n        return ans\n        \n```\nPLEASE UPVOTE ME, IF YOU LIKE THE SOLUTION.\n![7c17f983-3b8b-4738-b722-c1c1466f9510_1682940288.2823734.jpeg](https://assets.leetcode.com/users/images/a4a7bfa3-19ac-4a76-abfd-0514f70e7c77_1716523236.767006.jpeg)\n\n
['String', 'Stack', 'Greedy', 'Python', 'Python3']