Minimum Swaps for Bracket Balancing

Minimum Swaps for Bracket Balancing is a classic greedy warm-up. It shows how a single running counter — the open-bracket balance — tells you exactly when a string is broken and lets you fix it on the spot, without ever backtracking.

The slow way first

You could try every possible sequence of swaps and search for the shortest one that balances the string. That explodes combinatorially — far too slow for anything but a tiny input.

The question to ask: as I read left to right, when exactly does the string become illegal? It becomes illegal at the first ] that has no unmatched [ in front of it. If I can detect that instant cheaply, I can repair it greedily.

The idea: track the open-bracket balance

Keep a counter balance. Each [ adds 1, each ] subtracts 1. While balance stays at 0 or above, the prefix is still legal. The moment a ] would push balance below 0, we have an unmatched close — so we swap in the nearest unused [ from the right, count that swap, and continue. Every needed swap fixes exactly one violation, so the count is optimal.

The key insight: you never undo a swap. Each violation costs exactly one swap, so counting them as you go gives the minimum directly.

Walk through it

Step through the animation. The pointer i scans left to right while balance updates underneath. At index 0 a ] would drop balance to -1, so pointer j finds the next [ (index 2), swaps it in, and swaps becomes 1. The same thing happens later at index 2, giving a second swap. The scan ends with balance back at 0 and swaps = 2.

Pseudocode

chars = list of brackets
balance = 0
swaps = 0
for i from 0 to end of chars:
    if chars[i] is "[":
        balance += 1
    else:                         # it is "]"
        if balance > 0:
            balance -= 1          # legal close, just consume it
        else:
            find next j > i where chars[j] is "["
            swap chars[i] and chars[j]
            swaps += 1
            balance += 1          # the swapped-in "[" opens
return swaps

The Python solution

def min_swaps(s):
    chars = list(s)
    balance = swaps = 0
    for i in range(len(chars)):
        if chars[i] == "[":
            balance += 1
        else:
            if balance > 0:
                balance -= 1
            else:
                j = i + 1
                while chars[j] == "]":
                    j += 1
                chars[i], chars[j] = chars[j], chars[i]
                swaps += 1
                balance += 1
    return swaps

• balance is the count of currently unmatched [. It must never dip below 0 for a legal prefix.
• A [ simply raises balance; a ] with balance > 0 is a legal close, so we lower balance.
• The else branch is the violation case: a ] with balance == 0. We scan forward for the nearest [ and swap it into place.
• After the swap, that position now holds [, so balance rises and swaps increments by one.
• Because each swap repairs exactly one unmatched close, the running swaps total is already the minimum.

Complexity

The inner while that hunts for the next [ never re-scans the same region twice across the whole run, so the total work stays linear. We use O(n) space to hold the bracket list as a mutable array.

When this pattern shows up

Practice