Minimum Number of Swaps to Make the String Balanced Solution
Minimum Number of Swaps to Make the String Balanced solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Number of Swaps to Make the String Balanced is a medium coding problem on strings, greedy and two pointers, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Greedy, Two Pointers, Stack
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string s of even length containing exactly n/2 opening brackets '[' and n/2 closing brackets ']'.
In one move you may swap any two characters. Return the minimum number of swaps needed to make the string balanced.
Example 1
Input: s = "][]["
Output: 1
Example 2
Input: s = "]]][[["
Output: 2
Example 3
Input: s = "[]"
Output: 0
Constraints
2 <= s.length <= 40s.length is even.s contains equally many '[' and ']'.
Hints for Minimum Number of Swaps to Make the String Balanced
Hint 1
Cancel matched pairs as you scan; what remains is a block of
]followed by a block of[, of equal size.Hint 2
One well-chosen swap fixes two of the unmatched pairs at once.
Hint 3
So the answer is the number of unmatched pairs, rounded up after halving.
How to solve Minimum Number of Swaps to Make the String Balanced
Cancel matched pairs; what remains is ]]…[[ with u unmatched of each, and one swap fixes two of them, so the answer is ⌈u / 2⌉.
Approach
- Scan counting unmatched
[; a]cancels one if available. - Return
(unmatched + 1) // 2.
Why it works
After cancelling, the leftover is u closers followed by u openers; swapping the first ] with the last [ balances two pairs at once, and no swap can fix more than two.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The count of unmatched
]equals the count of unmatched[because the totals are equal.
Reference solution
Python
def minSwaps(s: str) -> int:
unmatched = 0
for ch in s:
if ch == "[":
unmatched += 1
elif unmatched > 0:
unmatched -= 1
return (unmatched + 1) // 2Java
public static int minSwaps(String s) {
int unmatched = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '[') unmatched++;
else if (unmatched > 0) unmatched--;
}
return (unmatched + 1) / 2;
}C++
int minSwaps(string s) {
int unmatched = 0;
for (char c : s) {
if (c == '[') unmatched++;
else if (unmatched > 0) unmatched--;
}
return (unmatched + 1) / 2;
}JavaScript
var minSwaps = function(s) {
let unmatched = 0;
for (let i = 0; i < s.length; i++) {
if (s.charAt(i) === "[") unmatched++;
else if (unmatched > 0) unmatched--;
}
return Math.floor((unmatched + 1) / 2);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Greedy Algorithms