Python | Greedy Pattern
see the Successfully Accepted Submission\n\n# Code\npython3 []\nclass Solution:\n    def minAddToMakeValid(self, s: str) -> int:\n        # Initialize balance v
[see the Successfully Accepted Submission](https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/submissions/1416537063/?envType=daily-question&envId=2024-10-09)\n\n# Code\n```python3 []\nclass Solution:\n    def minAddToMakeValid(self, s: str) -> int:\n        # Initialize balance variables for unmatched parentheses\n        left_balance = 0  # Tracks unmatched \'(\'\n        right_balance = 0  # Tracks unmatched \')\'\n        \n        # Traverse through the string\n        for char in s:\n            if char == \'(\':\n                left_balance += 1  # Add an unmatched \'(\'\n            elif char == \')\':\n                if left_balance > 0:\n                    # If there is an unmatched \'(\', pair it with this \')\'\n                    left_balance -= 1\n                else:\n                    # If no unmatched \'(\', this \')\' is unmatched\n                    right_balance += 1\n        \n        # The total moves needed is the sum of unmatched \'(\' and \')\'\n        return left_balance + right_balance\n\n```\n\n## Approach:\nWe can solve this problem by using a greedy approach with a simple counter. The idea is to scan through the string and keep track of:\n\n- The number of unmatched opening parentheses `(`.\n- The number of unmatched closing parentheses `)`.\n\nWe maintain two variables:\n\n- **left_balance**: Tracks how many opening parentheses `(` are currently unmatched.\n- **right_balance**: Tracks how many closing parentheses `)` are unmatched due to either extra `)` or missing `(`.\n\n### Steps:\n1. **Iterate through the string**:\n    - If we encounter an opening parenthesis `(`, we increment the `left_balance` because it means we have an additional opening parenthesis that needs to be matched.\n    - If we encounter a closing parenthesis `)`, we need to check if there is an unmatched opening parenthesis in the `left_balance` to pair with. If there is, we decrement the `left_balance`. If not, we increment `right_balance` because this closing parenthesis is unmatched and needs an opening parenthesis to pair with.\n\n2. **Result**:\n    - After processing the string, any remaining unmatched opening parentheses in `left_balance` will need closing parentheses to balance them.\n    - Any remaining unmatched closing parentheses in `right_balance` will need opening parentheses to balance them.\n\n3. **The total number of parentheses needed** will be the sum of `left_balance` and `right_balance`.\n\n---\n\n## Explanation of the code:\n- `left_balance` keeps track of how many opening parentheses `(` are currently unmatched.\n- `right_balance` counts the number of unmatched closing parentheses `)`.\n- After processing the entire string, `left_balance` will hold the count of unmatched opening parentheses and `right_balance` will hold the count of unmatched closing parentheses.\n- The total number of insertions required is the sum of these two values.\n\n---\n\n### Time Complexity:\n- **O(n)** where `n` is the length of the string. We traverse the string once.\n\n### Space Complexity:\n- **O(1)**, as we only use a constant amount of extra space.\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']