Minimum number of swaps for bracket balancing

Problem Statement

Given a string containing only brackets [ and ], find the minimum number of swaps needed to make the string balanced. A balanced string has all opening brackets closed by corresponding closing brackets in the correct order.

Example:

• Input: "]][["
• Output: 2
• Explanation: Swap positions (0,3) and (1,2) to get "[[]]"

Example 2:

• Input: "][]["
• Output: 1
• Explanation: Swap positions (0,1) to get "[][]"

Approach 1: Brute Force (Simulation)

Intuition

Simulate the process: traverse the string, track imbalance. When we find an unmatched ], find the nearest [ after it and swap.

Algorithm

1. Convert string to character array (for swapping)
2. Traverse left to right, track open bracket count
3. When count goes negative (unmatched ]), find next [ and swap
4. Increment swap counter
5. Continue until end

public class Solution {
    public int minSwaps(String str) {
        char[] s = str.toCharArray();
        int n = s.length;
        int swaps = 0;
        int openCount = 0;
        
        for (int i = 0; i < n; i++) {
            if (s[i] == '[') {
                openCount++;
            } else {
                if (openCount > 0) {
                    openCount--;
                } else {
                    // Unmatched ']', find next '[' and swap
                    int j = i + 1;
                    while (j < n && s[j] != '[') {
                        j++;
                    }
                    
                    // Swap s[i] and s[j]
                    char temp = s[i];
                    s[i] = s[j];
                    s[j] = temp;
                    swaps++;
                    openCount++;
                }
            }
        }
        
        return swaps;
    }
}

Complexity Analysis

• Time Complexity: O(n²) - For each unmatched ], we may search O(n) positions
• Space Complexity: O(n) - Converting string to array

Approach 2: Count Imbalance (Optimal)

Intuition

We don't actually need to perform swaps. We just need to count unmatched brackets. Each swap can fix 2 unmatched brackets. So the answer is (unmatched + 1) / 2.

Algorithm

1. Traverse string, track count of unmatched opening brackets
2. When we see [, increment count
3. When we see ]:
   • If count > 0, decrement (matched with previous [)
   • Otherwise, this is an unmatched ]
4. Count unmatched ] brackets
5. Answer = (unmatched + 1) / 2

public class Solution {
    public int minSwaps(String s) {
        int unmatchedOpen = 0;
        int unmatchedClose = 0;
        
        for (char c : s.toCharArray()) {
            if (c == '[') {
                unmatchedOpen++;
            } else {
                if (unmatchedOpen > 0) {
                    unmatchedOpen--;
                } else {
                    unmatchedClose++;
                }
            }
        }
        
        return (unmatchedClose + 1) / 2;
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n) - Single pass
• Space Complexity: O(1) - Only two counters

Approach 3: Stack-based (Alternative Optimal)

Intuition

Use a stack to match brackets. Count remaining unmatched after processing. This is conceptually similar to the counter approach but more explicit.

import java.util.*;

public class Solution {
    public int minSwapsStack(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (char c : s.toCharArray()) {
            if (c == '[') {
                stack.push(c);
            } else {
                if (!stack.isEmpty() && stack.peek() == '[') {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
        }
        
        int unmatchedPairs = stack.size() / 2;
        return (unmatchedPairs + 1) / 2;
    }
}

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n) - Stack storage

Why (unmatched + 1) / 2?

Consider unmatched brackets after removing all valid pairs:

Each swap can fix 2 unmatched brackets:

• Swapping '][' → '[]' fixes both brackets

For k unmatched ']' brackets:

• 1 unmatched: need 1 swap
• 2 unmatched: need 1 swap
• 3 unmatched: need 2 swaps
• 4 unmatched: need 2 swaps

Pattern: ceil(k/2) = (k + 1) / 2

Key Takeaways

1. Don't actually swap - Count unmatched brackets instead
2. Each swap fixes 2 brackets - This leads to the formula (unmatched + 1) / 2
3. The stack approach is more intuitive but uses O(n) space
4. The counter approach is O(1) space and equally efficient
5. This is a common bracket balancing problem variation
6. Similar logic applies to other bracket types: (), {}