Minimum swaps for bracket balancing

Medium

Problem

The string has n [ and n ] characters. In one swap you may exchange two adjacent characters. Return the minimum number of swaps needed to balance the string.

Example 1

Input:  "[]][]["
Output: 2

Example 2

Input:  "[[][]]"
Output: 0

Also asked as: Minimum number of swaps for bracket balancing

Test cases

Case 1

Input:    "[]][]["
Expected: 2

Case 2

Input:    "[[][]]"
Expected: 0

Case 3

Input:    "]["
Expected: 1

Case 4

Input:    "]]][[["
Expected: 6

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Track imbalance; each unmatched close costs its distance

Time O(n)Space O(1)

Scan; keep the running balance. On each unmatched "]", the number of swaps needed equals the count of "[" still waiting minus already-fixed — accumulate `imbalance` and add it when balance goes negative.

function minSwaps(s) {
let balance = 0, swaps = 0, imbalance = 0;
for (const c of s) {
if (c === '[') {
balance++;
if (imbalance > 0) { swaps += imbalance; imbalance--; }
} else {
balance--;
if (balance < 0) imbalance++;
}
}
return swaps;
}