Minimum Number of Swaps to Make the String Balanced

Minimum Number of Swaps to Make the String Balanced is LeetCode 1963, rated Medium. You are given a string s of even length n, consisting of exactly n/2 opening brackets [ and n/2 closing brackets ]. You can swap the brackets at any two indices any number of times. Return the minimum number of swaps to make the string balanced.

A string is balanced if it is empty, or can be written as [A] where A is balanced, or AB where A and B are both balanced.

Why this problem matters

Bracket balancing problems are everywhere in interviews. You have probably seen Valid Parentheses, which checks if a string is already balanced, and Minimum Remove to Make Valid Parentheses, which asks what to delete. This problem adds a twist: instead of removing characters, you swap them. The constraint that the string already has equal numbers of [ and ] is the key that makes a greedy solution possible.

This problem also teaches you to think about what a swap actually fixes. A single swap can repair two mismatches at once. Understanding that relationship between "number of defects" and "number of operations" is a pattern that shows up in many greedy problems.

The key insight

Once you cancel out all the matched pairs, you are left with some number of unmatched ] brackets followed by the same number of unmatched [ brackets. The unmatched portion always looks like ]]]...[[[... because all the correctly nested pairs have been absorbed.

Each swap takes one unmatched ] from the left and one unmatched [ from the right and puts them where they belong. That single swap fixes two unmatched brackets at once. So if there are k unmatched closing brackets, the answer is ceil(k / 2).

Why does one swap fix two? Consider ][. If you swap these two characters, you get [], which fixes both the misplaced ] and the misplaced [ in a single operation.

The approach

Scan the string left to right, keeping a balance counter:

1. When you see [, increment balance.
2. When you see ], decrement balance.
3. If balance goes negative, you have found an unmatched ]. Count it and reset balance to 0.

After scanning, the count of unmatched ] brackets tells you how many mismatches exist. Since each swap fixes two, the answer is (unmatchedClose + 1) // 2, which is the same as ceil(unmatchedClose / 2).

You do not need a stack for this. A single counter is enough because you only care about the count of mismatches, not their positions.

The solution

def minSwaps(s: str) -> int:
    unmatched = 0
    balance = 0

    for ch in s:
        if ch == '[':
            balance += 1
        else:
            balance -= 1

        if balance < 0:
            unmatched += 1
            balance = 0

    return (unmatched + 1) // 2

Step-by-step walkthrough

Let's trace through s = "]]][[[" . This is a worst case: all closing brackets come first, then all opening brackets. None of them are matched.

The scan finds 3 unmatched ] brackets. Each swap fixes 2, so we need ceil(3/2) = 2 swaps. After one swap, ]]][[[ becomes something like []]["[ which still has one mismatch. The second swap fixes the last one.

Complexity analysis

Time: O(n). A single pass through the string, doing constant work per character.

Space: O(1). Two integer variables (balance and unmatched). No stack, no extra array, no set.

This is optimal. You must read every character at least once to determine the answer, so O(n) time is a lower bound. And you cannot beat O(1) space.

Edge cases

• Already balanced: "[[]]" or "[[][]]". The balance never goes negative, so unmatched = 0 and the answer is 0.
• All opening then all closing: "[[[...]]]". Already balanced. Balance climbs up and then back down, never going negative.
• All closing then all opening: "]]]...[[[...". The worst case. Every ] at the start is unmatched, and the answer is ceil(n/4) since there are n/2 unmatched brackets.
• Alternating unbalanced: "][][". Balance goes to -1, resets, then climbs. unmatched = 1, answer is 1.
• Length 2: "][" needs 1 swap, "[]" needs 0.
• Empty string: The problem guarantees even length with at least 2 characters, but an empty string would return 0.

The building blocks

1. Greedy balance counting

The core pattern is scanning left to right with a balance counter. You increment on [ and decrement on ]. Whenever balance goes negative, you have detected a mismatch. This same counter-based approach appears in many bracket problems:

balance = 0
for ch in s:
    if ch == '[':
        balance += 1
    else:
        balance -= 1
    if balance < 0:
        # handle mismatch
        balance = 0

The trick in this problem is recognizing that you only need the mismatch count, not the positions. That lets you skip the stack entirely and work in O(1) space.

2. The "each operation fixes two" pattern

When an operation repairs multiple defects at once, the answer is ceil(defects / repair_per_op). Here, each swap fixes 2 unmatched brackets, so ceil(k / 2). This pattern appears in other greedy problems where you need to figure out the minimum number of operations.

From understanding to recall

You understand the greedy insight: scan for unmatched closing brackets, then divide by 2 and round up. The code is short, just a single loop with a balance counter. But will you remember it in three weeks?

The details that trip people up are small but important: remembering to reset balance to 0 when it goes negative, using integer division (k + 1) // 2 instead of importing math.ceil, and recognizing that you do not need a stack at all. These are exactly the kind of details that fade after a single solve.

Spaced repetition locks them in. You practice writing the balance scan from scratch at increasing intervals. After a few rounds, the code comes out automatically. You see "minimum swaps to balance brackets" and your hands type the loop before your brain fully processes the problem statement.

The greedy balance counting pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Valid Parentheses - The foundational stack-based bracket matching problem. This problem builds on the same matching logic but asks for swaps instead of validation.
• Generate Parentheses - Builds valid bracket strings from scratch using backtracking. Understanding what makes a string balanced connects directly to this problem.
• Minimum Remove to Make Valid Parentheses - Another "fix the brackets" problem, but by removal instead of swapping. Compare the stack-based approach there with the counter-based approach here.

CodeBricks breaks Minimum Number of Swaps to Make the String Balanced into its greedy balance counting building block and drills it independently with spaced repetition. You type the scan loop and the ceiling division from scratch until they are automatic. When a bracket balancing problem shows up in your interview, the solution comes without hesitation.