You are given a 0-indexed string s of even length n. The string consists of exactly n / 2 opening brackets '[' and n / 2 closing brackets ']'.
A string is called balanced if and only if:
AB, where both A and B are balanced strings, or[C], where C is a balanced string.You may swap the brackets at any two indices any number of times.
Return the minimum number of swaps to make s balanced.
Example 1:
Input: s = "][][" Output: 1 Explanation: You can make the string balanced by swapping index 0 with index 3. The resulting string is "[[]]".
Example 2:
Input: s = "]]][[[" Output: 2 Explanation: You can do the following to make the string balanced: - Swap index 0 with index 4. s = "[]][][". - Swap index 1 with index 5. s = "[[][]]". The resulting string is "[[][]]".
Example 3:
Input: s = "[]" Output: 0 Explanation: The string is already balanced.
Constraints:
n == s.length2 <= n <= 106n is even.s[i] is either '[' or ']'.'[' equals n / 2, and the number of closing brackets ']' equals n / 2.This approach involves traversing the string and counting the balance between opening and closing brackets. You increase a count when you find an opening bracket and decrease the count when you find a closing bracket. If at any point the count goes negative, a swap is needed to balance out the string, and the swap count is incremented. The final swap count will be the required number of swaps to make the string balanced.
This solution maintains a balance count by iterating over the characters of the string. It increases the balance for each opening bracket '[' encountered and decreases it for each closing bracket ']'. Whenever the balance goes negative, a swap is needed to make balance non-negative, hence the count of swaps is incremented along with a correction of balance at that point. This provides the minimum number of swaps needed.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of string s.
Space Complexity: O(1), as no extra space is used aside from a few variables.
This approach uses two pointers to traverse the string efficiently. One pointer starts from the beginning of the string, and the other starts at the end. Using these pointers, swaps are performed when an excessive number of closing brackets on one side can be paired with an opening bracket on the other side.
Two pointers are initialized at the start and end of the string. The inner mismatched brackets are swapped until the string becomes balanced. The solution ensures that excessive closing brackets found earlier are balanced by swapping them with opening brackets found later in the string.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of string s, due to traversing the string once.
Space Complexity: O(1), as we're only using constants amount of space for pointers and variables.
| Approach | Complexity |
|---|---|
| Greedy Approach Using Balance Count | Time Complexity: O(n), where n is the length of string s. |
| Two-Pointer Approach | Time Complexity: O(n), where n is the length of string s, due to traversing the string once. |
Minimum Number of Swaps to Make String Balanced - Leetcode 1963 Weekly Contest - Python • NeetCode • 47,493 views views
Watch 9 more video solutions →Practice Minimum Number of Swaps to Make the String Balanced with our built-in code editor and test cases.
Practice on FleetCode