Minimum Number of Swaps to Make the String Balanced

How it works

This approach directly simulates the stack without actually using a stack data structure. We use a counter stackSize that increments for [ and decrements for ] only if there is something to match (stackSize > 0). The final counter value represents unmatched opening brackets.

This is equivalent to the stack approach but uses O(1) space since we only track the count, not the actual characters.

Steps

1. Initialize stackSize = 0.
2. Iterate through the string:
   • If the character is [, increment stackSize.
   • If the character is ] and stackSize > 0, decrement stackSize.
3. Return (stackSize + 1) / 2.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Counting All Brackets Instead of Unmatched

The answer depends on unmatched brackets, not total brackets. Counting all [ or ] characters without first matching valid pairs will give an incorrect count. Only brackets that remain after matching contribute to the swap count.

Forgetting That One Swap Fixes Two Pairs

Each swap can fix two unmatched bracket pairs simultaneously. Returning the unmatched count directly instead of dividing by 2 (with ceiling) will double the actual number of swaps needed.

Popping From Empty Stack

When simulating with a stack, attempting to pop when encountering ] without checking if the stack is empty will cause runtime errors. Only pop if there is a matching [ available to pair with the current ].

class Solution:
    def minSwaps(self, s: str) -> int:
        stackSize = 0
        for c in s:
            if c == '[':
                stackSize += 1
            elif stackSize > 0:
                stackSize -= 1
        return (stackSize + 1) // 2

class Solution {
public:
    int minSwaps(string s) {
        int stackSize = 0;
        for (auto& c : s) {
            if (c == '[') stackSize++;
            else if (stackSize > 0) stackSize--;
        }
        return (stackSize + 1) / 2;
    }
};