Minimum Number of Swaps to Make the String Balanced
Asked at Visa
Problem
Minimum Number of Swaps to Make the String Balanced gives you a string of equally many [ and ] characters and asks for the fewest swaps (of any two positions) to make the brackets balanced. After cancelling every matched pair, what remains is always ]]]...[[[, and one swap fixes two of the leftover pairs.
Asked At
| Company | Difficulty | |
|---|---|---|
| Visa | Medium | View all Visa questions → |
How to Think About It
Matched pairs never need to move. Cancel them with a stack (or just a counter of open brackets).
What is left after cancelling is some number m of ] followed by m of [, like ]]][[[.
Key insight: one swap of the first unmatched ] with the last unmatched [ turns ]...[ into [...] and fixes two pairs at once (the swapped pair and the one next to it). So the answer is ceil(m / 2).
Count m with one variable: open tracks unmatched [. On ], if open > 0 it matches (open -= 1), otherwise it is an unmatched ] (m += 1).
Walkthrough: "]]][[[": m = 3 -> (3 + 1) // 2 = 2 swaps.
Optimal Approach
Step 1: open = 0, unmatched = 0.
Step 2: For each char: [ -> open += 1; ] -> if open > 0, open -= 1, else unmatched += 1.
Step 3: Return (unmatched + 1) // 2.
Time: O(n). Space: O(1).
What Trips People Up in Real Interviews
Answering m swaps instead of ceil(m / 2). Each well-chosen swap fixes two pairs.
Simulating swaps on the string. Only the count matters.
Confusing swaps with insertions or deletions (as in Minimum Add to Make Parentheses Valid).
Not justifying why the leftover pattern is always ]...][...[.
Solution Code
def minSwaps(s):
open_count = unmatched = 0
for ch in s:
if ch == '[':
open_count += 1
elif open_count > 0:
open_count -= 1
else:
unmatched += 1
return (unmatched + 1) // 2Frequently Asked Questions
What is the Minimum Number of Swaps to Make the String Balanced problem?
Minimum Number of Swaps to Make the String Balanced gives you a string of equally many `[` and `]` characters and asks for the fewest swaps (of any two positions) to make the brackets balanced. After cancelling every matched pair, what remains is always `]]]...[[[`, and one swap fixes two of the leftover pairs.
How do you solve Minimum Number of Swaps to Make the String Balanced?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Minimum Number of Swaps to Make the String Balanced?
Minimum Number of Swaps to Make the String Balanced is asked at Visa. It is a medium difficulty problem.
What are common mistakes on Minimum Number of Swaps to Make the String Balanced?
- Answering `m` swaps instead of `ceil(m / 2)`. Each well-chosen swap fixes two pairs.
- Simulating swaps on the string. Only the count matters.
- Confusing swaps with insertions or deletions (as in Minimum Add to Make Parentheses Valid).
- Not justifying why the leftover pattern is always `]...][...[`.