Fewest Arbitrary Bracket Swaps
Company: Infosys
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
The even-length string `s` contains equally many `[` and `]` characters. One operation swaps the characters at any two indices. Return the smallest number of operations needed to make the string balanced: every prefix must have at least as many openings as closings, and the total counts must agree.
```cpp
class Solution {
public:
int minSwaps(string s);
};
```
### Examples
**Example 1:**
```text
s = "]["
Output: 1
Explanation: Exchanging the two brackets produces "[]".
```
**Example 2:**
```text
s = "]][["
Output: 1
Explanation: Swapping indices 0 and 3 produces "[][]".
```
### Constraints
- `2 <= s.length <= 10^6`; the length is even.
- Characters are `[` or `]`, with exactly half of each.
### Clarifying Questions
Swaps may use any two positions. The resulting string must satisfy the stated balanced-bracket definition.
```hint Inspect the structure
By how much can one swap improve the worst prefix deficit?
```
### Reasoning checkpoints
- Prove both a lower bound on arbitrary swaps and that a sequence attaining it exists.
- Handle an already balanced string and distinguish arbitrary-index swaps from adjacent swaps.
### Optional extensions
How does the minimum operation count change if only adjacent brackets may be swapped?
Overview: Fewest Arbitrary Bracket Swaps. The even-length string s contains equal numbers of opening and closing square brackets. Swap characters at any two indices to make every prefix contain at least as many openings as closings. Return the minimum number of swaps.