Beats 90.40 % of Solutions 🔥🔥🔥. Minimum Number of Swaps to Make the String Balanced. 😉
Intuition\nThe string consists of an equal number of opening [ and closing ] brackets, but they might be arranged incorrectly, creating an imbalance. The goal i
# Intuition\nThe string consists of an equal number of opening [ and closing ] brackets, but they might be arranged incorrectly, creating an imbalance. The goal is to find the minimum number of swaps required to make the string balanced. To solve this, we can track the imbalance between the closing and opening brackets. A high imbalance indicates that too many closing brackets have appeared without a corresponding opening bracket, which would require swaps to correct.\n\n# Approach\n[01] Initialization: \n--------------------------------------\n\nWe start by setting up two variables:\nib (imbalance): Tracks the current imbalance between closing and opening brackets.\nmb (max imbalance): Tracks the maximum imbalance encountered during the traversal of the string.\n\n[02] Iterating through the string:\n--------------------------------------\n\nFor each character in the string:\nIf the character is [, we reduce the imbalance (ib--) since an opening bracket reduces the imbalance caused by previous ].\nIf the character is ], we increase the imbalance (ib++) since a closing bracket increases the imbalance unless there is a corresponding [.\n\n[03] Tracking the maximum imbalance: \n--------------------------------------\n\nAfter each iteration, we update mb to be the maximum between the current imbalance and the previously recorded maximum imbalance.\n\n[04] Calculating the minimum swaps:\n--------------------------------------\n\nOnce the maximum imbalance is determined, the number of swaps required to correct it is given by (mb + 1) / 2. This formula works because each swap can fix two imbalanced brackets.\n\n# Complexity\n- Time complexity:\nThe algorithm iterates through the string once, so the time complexity is O(n) where n is the length of the string.\n\n- Space complexity:\nThe algorithm uses only a few extra variables (ib and mb), so the space complexity is O(1).\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    Solution() {\n        ios_base::sync_with_stdio(0);\n        cin.tie(0);\n        cout.tie(0);\n    }\n\n    int minSwaps(string s) {\n        int ib = 0, mb = 0;\n        for (char c : s) {\n            if (c == \'[\') {\n                ib--;\n            } else {\n                ib++;\n            }\n            mb = max(mb, ib);\n        }\n        return (mb + 1) / 2;\n    }\n};\n```
['C++']