Minimum swaps for bracket balancing
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
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;}