Watch 10 video solutions for Minimum Number of Swaps to Make the String Balanced, a medium level problem involving Two Pointers, String, Stack. This walkthrough by NeetCode has 51,204 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: You are given a string consisting only of '[' and ']'. The string contains equal numbers of both brackets but may be unbalanced. The goal is to compute the minimum number of swaps needed to transform it into a valid balanced bracket sequence.
Approach 1: Greedy Using Balance Count (O(n) time, O(1) space)
This approach scans the string once while tracking the current bracket balance. Increment the balance for '[' and decrement for ']'. When the balance becomes negative, it means a closing bracket appears before a matching opening bracket. At that point you conceptually perform a swap with a future '['. Each time this happens, increase the swap counter and reset the balance to 1 because the swap effectively inserts a valid opening bracket before the closing one.
The key insight is that you never need to physically perform swaps. Counting imbalance is enough because every time the prefix becomes invalid, one swap will fix it. This greedy logic works since each correction locally restores validity and guarantees the minimal number of swaps. The method runs in linear time and constant space and is the cleanest solution for this problem. This pattern commonly appears in greedy and string balancing problems.
Approach 2: Two-Pointer Swap Simulation (O(n) time, O(1) space)
The two-pointer strategy simulates the swaps explicitly. Maintain a left pointer scanning for imbalance and a right pointer searching for the next available '[' that can fix it. When the prefix becomes invalid (more ']' than '['), move the right pointer backward until a '[' is found and swap it with the problematic closing bracket.
This technique directly demonstrates why each imbalance requires a swap. After the swap, continue scanning from the left while maintaining the balance count. The algorithm still runs in O(n) time because each pointer moves at most once across the string. This approach is useful for understanding the mechanics of fixing invalid bracket sequences and often appears in problems using two pointers or stack-like validation logic.
Recommended for interviews: The greedy balance-count approach is what interviewers usually expect. It shows you recognize the imbalance pattern and can solve it with a single pass and constant memory. Demonstrating the two-pointer simulation first can help explain the intuition, but the greedy counting method highlights stronger algorithmic insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Using Balance Count | O(n) | O(1) | Best general solution; minimal logic and optimal complexity |
| Two-Pointer Swap Simulation | O(n) | O(1) | Useful for understanding how swaps fix imbalance step by step |