1963. Minimum Number of Swaps to Make the String Balanced
Approach
Count unmatched ']' after cancelling matched pairs; answer = ceil(unmatched / 2).
Key Techniques
The two-pointer technique places pointers at different positions (often the two ends) and moves them toward each other. It turns O(n²) nested loops into O(n) sweeps for problems like pair sums, removing duplicates, and container capacity. Works best on sorted or partitioned arrays.
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
// Approach: Count unmatched ']' after cancelling matched pairs; answer = ceil(unmatched / 2).
// Time: O(n) Space: O(1)
public class Solution
{
public int MinSwaps(string s)
{
// Cancel out all the matched pairs, then we'll be left with "]]]..[[[".
// The answer is ceil(the number of unmatched pairs / 2).
int unmatched = 0;
foreach (char c in s)
{
if (c == '[')
{
unmatched++;
}
else if (unmatched > 0)
{ // c == ']' and there's a match.
unmatched--;
}
}
return (unmatched + 1) / 2;
}
}