Given a string of square brackets '[' and ']', you need to find the minimum number of swaps to make the string balanced. A balanced string is one where every opening bracket has a corresponding closing bracket in the correct order. Interestingly, you can swap any two characters, and you want to achieve balance in the fewest moves possible.
This is a popular question at companies like Microsoft, Google, and Adobe because it requires a clever observation that simplifies the problem. While it looks like a stack problem (which it is, initially), the "swap" aspect adds a greedy layer. It tests if a candidate can see through the complexity to find a simple mathematical relationship between "unbalanced" pairs and the number of swaps.
The pattern is Greedy with a Stack-based logic (though you can simulate the stack with a simple counter). You traverse the string and remove all balanced pairs. You'll be left with a string of the form "]]][[[". The number of swaps needed to fix k unbalanced pairs is (k + 1) / 2.
String: "][]["
Many try to use a standard stack and perform actual swaps in a simulation, which is difficult and prone to errors. Others struggle to derive the (k+1)/2 formula. A frequent mistake is thinking you need to swap every single unbalanced bracket, whereas a single swap can actually resolve two unbalanced pairs if done strategically.
For bracket problems, always start by "canceling out" valid pairs. Whatever remains is the core of the problem. Often, the remaining string will have a very predictable structure (like all ']' followed by all '['), making it much easier to solve.
| Title | Difficulty | Topics | LeetCode |
|---|---|---|---|
| Check if a Parentheses String Can Be Valid | Medium | Solve | |
| Maximum Score From Removing Substrings | Medium | Solve | |
| Minimum Add to Make Parentheses Valid | Medium | Solve | |
| Append Characters to String to Make Subsequence | Medium | Solve | |
| Separate Black and White Balls | Medium | Solve |
