67. Minimum Swaps for Bracket Balancing

Given a string s of only [ and ] characters with an equal total count of each, find the minimum number of swaps needed to balance it, where a swap exchanges any two characters in the string.

Input: The input is a single line containing a string s of '[' and ']' characters, with equal counts of each; it may be empty. Output: Print a single integer - the minimum number of swaps needed to balance s.

0 <= |s| <= 10^5, count of '[' equals count of ']'

This is a genuinely different (and more general) problem than simply counting UNMATCHED brackets and flipping them - here you're allowed to swap ANY two characters anywhere in the string, not just flip individual ones, which is exactly why the formula and technique differ from the 'reversal' variant of this problem family.

Given a string of only [ and ] with equal counts of each, find the fewest character SWAPS (exchanging any two characters anywhere) needed to make it balanced. Brute force: Try every possible sequence of swaps directly, searching for the shortest sequence that results in balance - this branches combinatorially and is impractical to search directly. Optimised: Tracking the running imbalance (specifically, how deep the string ever gets into 'more unmatched closers than openers' territory) directly measures how badly tangled the worst point in the string is - and since a single swap can pull a needed '[' from anywhere later in the string to resolve TWO units of imbalance at once, the maximum imbalance divided by two (rounded up) is provably the true minimum swap count.

Repeatedly scan the string left to right tracking balance; the first time an unmatched ']' is found (balance would go negative), search forward for the nearest '[' and physically swap the two characters, incrementing the swap counter, then restart the scan from the beginning. This directly mirrors what the problem describes and is easy to verify as correct, but rescanning from the start after every single swap makes it quadratic in the worst case. Time: O(n^2) Space: O(n)

Scan the string once maintaining a simple balance counter that increments on '[' and decrements on ']'; whenever the balance would go negative (an unmatched ']'), increment a separate imbalance counter and reset balance to 0 rather than tracking or performing any actual swap. At the end, the minimum number of swaps needed equals ceil(imbalance / 2), since each swap can simultaneously fix two units of imbalance in a run of unmatched closing brackets. This reaches the answer with pure counting, no auxiliary positions or explicit swaps tracked at all, using only constant extra space. Time: O(n) Space: O(1)

Use one forward pointer to scan the string while tracking the running balance, and whenever an unmatched ']' is found, use a second pointer (continuing from where it left off, never restarting) to find and swap in the nearest available '[' from later in the string, recording the swap. Because both pointers only ever move forward, the whole string is processed in a single overall pass rather than being repeatedly rescanned, at the cost of keeping explicit position/state tracking in memory. Time: O(n) Space: O(n)

1. Scan the string left to right, tracking a running 'imbalance': increase it whenever you see an unmatched ']' (a closing bracket with no available opener), and decrease it back toward 0 whenever a '[' appears while imbalance is positive. 2. Track the LARGEST imbalance value reached at any point during this scan. 3. The answer is ceil(maxImbalance / 2), since each swap can fix two units of imbalance at once (bringing a distant '[' forward to cancel two unmatched ']'s).

Time: O(n) - a single linear pass through the string, tracking a running imbalance counter. Space: O(1) - just the running imbalance and its maximum value seen so far.

An empty string (0 swaps); a string already balanced (0 swaps); a large maximum running imbalance requiring the ceil(maxImbalance/2) computation; s up to 10^5 characters for performance.

Be ready to justify why a single swap fixes exactly TWO units of imbalance, not one - this is the crucial insight behind the ceil(maxImbalance/2) formula, and interviewers often ask for this justification specifically.