Solution Explanation: Greedy Approach

This problem can be efficiently solved using a greedy approach. The core idea is to track the imbalance between opening and closing brackets as we iterate through the string. We don't need to perform actual swaps; instead, we count the minimum number of swaps required.

Algorithm:

1. Initialization: Initialize a counter x to 0. This counter will keep track of the excess opening brackets.

2. Iteration: Iterate through the input string s.

   • If the character is an opening bracket ([): Increment x (we have an unmatched opening bracket).
   • If the character is a closing bracket (]):
     • If x > 0 (we have unmatched opening brackets), decrement x (match the closing bracket with an existing unmatched opening bracket). This is the greedy part; we immediately try to match closing brackets with the closest available opening brackets.

3. Final Calculation: After iterating through the entire string, x represents the number of remaining unmatched opening brackets. To balance the string, we need to swap pairs of brackets. Each pair of swaps involves one unmatched opening bracket and one unmatched closing bracket. Therefore, the minimum number of swaps required is (x + 1) // 2 (integer division). We add 1 because even if x is 1 we need to perform one swap.

Time and Space Complexity:

• Time Complexity: O(n), where n is the length of the string. We iterate through the string once.
• Space Complexity: O(1). We only use a constant amount of extra space to store the counter x.

Code Implementation (Python):

class Solution:
    def minSwaps(self, s: str) -> int:
        x = 0
        for c in s:
            if c == "[":
                x += 1
            elif x > 0:  # Only decrement if there are unmatched opening brackets
                x -= 1
        return (x + 1) // 2  # Integer division to get the minimum number of swaps

Code Implementation (Java):

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

Code Implementation (C++):

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

Code Implementation (Go):

func minSwaps(s string) int {
	x := 0
	for _, c := range s {
		if c == '[' {
			x++
		} else if x > 0 {
			x--
		}
	}
	return (x + 1) / 2
}
 

Code Implementation (Javascript):

/**
 * @param {string} s
 * @return {number}
 */
var minSwaps = function(s) {
    let x = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '[') {
            x++;
        } else if (x > 0) {
            x--;
        }
    }
    return Math.floor((x + 1) / 2);
};

Code Implementation (Typescript):

function minSwaps(s: string): number {
    let x = 0;
    for (const c of s) {
        if (c === '[') {
            x++;
        } else if (x > 0) {
            x--;
        }
    }
    return Math.floor((x + 1) / 2);
}

All the code implementations above follow the same greedy algorithm, differing only in syntax. They all achieve a time complexity of O(n) and a space complexity of O(1).