Back to solutions

Minimum Number of Swaps to Make The String Balanced

MediumArrays

Fewest swaps to balance a string of brackets.

Open problem
Constraints
  • 2 <= length <= 10^6
  • equal counts of '[' and ']'

Track the deepest deficit

Time O(n)Space O(1)

Treat '[' as +1 and ']' as -1 and track the running balance. The most negative balance reached is the deepest 'deficit' of unmatched closing brackets. Each swap can fix two of these mismatches, so the answer is ceil(deficit / 2), computed as (-minBalance + 1) / 2.

Key terms
balance:
Running count of opens minus closes; negative means too many closes so far.
deficit:
The largest shortfall of opening brackets, i.e. the most negative balance.
int minSwaps(const string& s) {
    int balance = 0, maxDeficit = 0;
    for (char c : s) {
        balance += (c == '[') ? 1 : -1;
        maxDeficit = min(maxDeficit, balance);
    }
    return (-maxDeficit + 1) / 2;
}
Step by step
  1. Walk the string, adding +1 for '[' and -1 for ']' to a running balance.
  2. Record the minimum (most negative) balance seen.
  3. The number of unmatched closers at the worst point is -minBalance.
  4. Each swap fixes two, so return ceil(-minBalance / 2) = (-minBalance + 1) / 2.