Python | Greedy & Counting Patterns
see the Successfully Accepted Submission\n\n# Code\npython3 []\nclass Solution:\n    def minSwaps(self, s: str) -> int:\n        balance = 0\n        max_imbala
[see the Successfully Accepted Submission](https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/submissions/1415420664/?envType=daily-question&envId=2024-10-08)\n\n# Code\n```python3 []\nclass Solution:\n    def minSwaps(self, s: str) -> int:\n        balance = 0\n        max_imbalance = 0\n        \n        # Traverse the string\n        for char in s:\n            if char == \'[\':\n                balance += 1  # Opening bracket, increase balance\n            else:\n                balance -= 1  # Closing bracket, decrease balance\n            \n            # Track the maximum imbalance (i.e., the maximum negative balance)\n            if balance < 0:\n                max_imbalance = max(max_imbalance, -balance)\n        \n        # The number of swaps needed is half of the max imbalance\n        # because each swap fixes two imbalances (one opening, one closing).\n        return (max_imbalance + 1) // 2\n\n```\n\n# Problem Breakdown\n\n### Balanced String Definition:\nA string is balanced if:\n1. It is empty.\n2. It can be written as the concatenation of two balanced strings.\n3. It can be written as `[C]` where `C` is a balanced string.\n\n### Invalid Patterns:\n- A closing bracket `]` without a matching opening bracket `[` before it indicates an imbalance.\n- We can fix this by swapping, where a closing bracket `]` can be swapped with an opening bracket `[`.\n\n# Strategy:\nThe main idea is to:\n1. **Track the "balance"** of brackets as we traverse the string.\n2. If we find a closing bracket `]` that does not have a preceding unmatched opening bracket `[`, we need to swap it later with an unmatched opening bracket `[`.\n\nTo solve this:\n- **Balance count**: As we iterate through the string, maintain a balance count:\n  - Increase the balance for every opening bracket `[`.\n  - Decrease the balance for every closing bracket `]`.\n- **Excess closing brackets**: If the balance becomes negative at any point, it indicates that we have more closing brackets `]` than opening brackets `[`. We need to swap at this point.\n\nThe number of swaps required corresponds to the number of times the balance goes negative, because that indicates we have an excess closing bracket that needs to be fixed.\n\n# Algorithm:\n1. Initialize a `balance` to 0.\n2. Traverse the string:\n   - For every `[` (opening bracket), increase the balance.\n   - For every `]` (closing bracket), decrease the balance.\n   - If the balance becomes negative, it means there are more closing brackets than opening brackets. This requires a swap, and we reset the balance.\n3. The number of swaps needed is proportional to the maximum imbalance encountered.\n\n# Explanation of the Code:\n### Balance tracking:\n- We track the balance between `[` and `]`.\n- If balance goes negative, it means we have an unmatched `]` that requires a swap.\n\n### Maximum imbalance:\n- The maximum imbalance (i.e., when the balance is most negative) tells us how many swaps we need to make.\n- Each swap fixes two positions: one `[` and one `]`. Thus, the number of swaps required is the maximum imbalance divided by 2.\n\n# Time Complexity:\n- **O(n)**: We traverse the string once to compute the balance.\n\n# Space Complexity:\n- **O(1)**: We only use a few variables for tracking the balance and maximum imbalance.\n\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']