671. Fewest Swaps to Balance the Brackets
A string of square brackets is given with exactly as many [ as ]. One move swaps ANY two
characters, not necessarily adjacent.
Print the fewest moves needed to make the string balanced, meaning every ] has a matching
[ before it.
]]][[[ -> 2
][][ -> 1
[] -> 0
## Measure how badly it fails
Walk the string keeping a running balance: +1 for [ and -1 for ]. The string is
balanced exactly when the balance never goes negative and ends at zero.
Since the counts are equal, the balance always ENDS at zero. So the only failure is dipping below zero, and how far it dips is what matters.
Let worst be the most negative the balance reaches, and need = -worst.
## One swap fixes two units of deficit
answer = ceil(need / 2)
Taking a [ from somewhere after the dip and putting it before the dip raises the balance at
the dip by 1, and lowers the later region by 1. But the swap also moves a ] from the front to
the back, which raises the dip by a further 1.
So one swap improves the deficit by 2, and ceil(need / 2) swaps are needed.
## Why it is achievable, not just a lower bound
The obvious choice is to swap the leftmost unmatched ] with the rightmost unmatched [.
Those always exist while the deficit is positive, because an unmatched ] means there is a
surplus [ later to balance the equal counts.
Each such swap repairs the two deepest units of deficit, so the bound is reached exactly.
## Where the two pointers are
The repair is a converging sweep: one pointer scanning from the left for an unmatched ], one
from the right for an unmatched [. The counting formula above is that sweep collapsed into a
single number, which is why no actual swapping is needed to answer the question.
## Boundaries
An already balanced string answers 0. ][ answers 1 and is the smallest failure.
]]][[[ answers 2, not 3: the deficit reaches 3, and ceil(3 / 2) is 2.
## Cost
Time O(n). Space O(1).
Constraints - `2 ≤ length ≤ 200000` and the length is even - the string contains only `[` and `]`, in equal numbers
Input
One line containing a string of [ and ] with equal numbers of each.
Output
Print one integer, the fewest swaps needed.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.