Minimum Number of Swaps to Make The String Balanced
You are given a string s[]
Example 1
Output: 1
Explanation: swap index 0 with index 3 to get "[[]]".
Example 2
Output: 2
Explanation: swap 0 with 4 to get "[]][][", then 1 with 5 to get "[[][]]".
Example 3
Output: 0
How to Think About It
Step 1: Cancel what already matches
Scan from left to right. Every ][]]]...[[[m
Step 2: One swap fixes two
Swap the first leftover ][
Step 3: The formula
So m leftover pairs need ceil(m / 2) = (m + 1) / 2
Step 4: Counting m
Keep open[]openunmatched
Walkthrough
s = "]]][[["
| Character | open after | unmatched after |
|---|---|---|
| ] | 0 | 1 |
| ] | 0 | 2 |
| ] | 0 | 3 |
| [ [ [ | 3 | 3 |
m = 3, so (3 + 1) / 2 = 2 swaps.
Java Solution
No swaps are actually made; only the count of leftover brackets is needed.
public class MinimumNumberOfSwapsToMakeTheStringBalanced {
public static int minSwaps(String s) {
int open = 0; // '[' still waiting for a match
int unmatched = 0; // ']' with no '[' before them
for (char c : s.toCharArray()) {
if (c == '[') {
open++;
} else if (open > 0) {
open--; // this ']' closes an earlier '['
} else {
unmatched++;
}
}
return (unmatched + 1) / 2; // each swap fixes two unmatched ']'
}
public static void main(String[] args) {
System.out.println(minSwaps("][][")); // 1
System.out.println(minSwaps("]]][[[")); // 2
System.out.println(minSwaps("[]")); // 0
}
}
The original implementation,
Complexity
- Time: O(n).
- Space: O(1).
Matching brackets with a counter, or with a stack when there are several kinds, is the basis of