Minimum Number of Swaps to Make the String Balanced

Count the worst prefix deficit

For the common problem with equal numbers of [ and ] and arbitrary swaps allowed, scan the string with balance += 1 for [ and -1 for ]. Whenever balance becomes negative, record the largest deficit and reset the conceptual balance as needed to continue measuring unmatched closings. Each swap can exchange an early unmatched ] with a later [, repairing two units of deficit, so the answer is (maxDeficit + 1) / 2. An equivalent implementation counts unmatched closings directly.

Check the operation model

This formula applies to swapping any two positions. If only adjacent swaps are allowed, positions of opening brackets must be tracked and the cost is much larger; if insertions are allowed, it is a different problem. Explain why every prefix of a balanced bracket string must have at least as many opens as closes, and a swap can eliminate two offending closings. The scan is O(n) time and O(1) space for arbitrary swaps. Test already balanced input, ]]][[[, alternating brackets, and invalid unequal counts if those are not guaranteed away.