Problem

You are given a 0-indexed string s of even length n. The string consists of exactly n / 2 opening brackets '[' and n / 2 closing brackets ']'.

A string is called balanced if and only if:

  • It is the empty string, or
  • It can be written as AB, where both A and B are balanced strings, or
  • It can be written as [C], where C is a balanced string.

You may swap the brackets at any two indices any number of times.

Return the minimum number of swaps to make s balanced.

Examples

Example 1:

Input s = "][]["
Output 1
Explanation You can make the string balanced by swapping index 0 with index 3.
The resulting string is "[[]]".

Example 2:

Input s = "]]][[["
Output 2
Explanation You can do the following to make the string balanced:
- Swap index 0 with index 4. s = "[]][][".
- Swap index 1 with index 5. s = "[[][]]".
The resulting string is "[[][]]".

Example 3:

Input s = "[]"
Output 0
Explanation The string is already balanced.

Solution

Method 1 - Count the imbalances

Count the number of mismatches, either by using stack OR counter variable, as there is only 1 type of parenthesis. We had done something similar here - Valid Parentheses Problem.

  • The given string has equal numbers of '[' and ']'.
  • To make the string balanced, we need sufficiently many '[' before ']' in the sequence.
  • What causes imbalance? It is a closing bracket before opening bracket.
  • The strategy involves tracking imbalances using a counter: when a closing bracket appears without a matching opening bracket, we record an imbalance and look for an opening bracket in future indices to swap it with.

We can ignore the balanced segments of the input string since they don’t affect the overall balance. Once we remove these, the remaining unbalanced brackets will appear as follows:

]]]]]…..[[[[[…..

Given that any pair of brackets can be swapped, the most efficient strategy is to balance two sets of brackets with a single swap (suggesting result = total unbalanced / 2, which applies to both even and odd lengths). For example:

So, following this, we will notice a pattern (try out the same with different number of mismatches to see the pattern):

swaps:      0, 1, 1, 2, 2, 3, 3..
imbalances: 0, 1, 2, 3, 4, 5, 6...

So, our result (min. swaps) = (mismatches + 1) / 2

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

Java
public class Solution {
    public int minSwaps(String s) {
        int imbalance = 0;  // To track the maximum imbalance of closing brackets
        int count = 0;  // To track the current imbalance of brackets

        // Iterate through each character in the string
        for (char ch : s.toCharArray()) {
            if (ch == '[') {
                count--;  // Decrease count for opening bracket
            } else {  // char is `']'`
                count++;  // Increase count for closing bracket
                if (count > imbalance) {
                    imbalance = count;  // Update the maximum imbalance
                }
            }
        }

        // The minimum number of swaps needed to balance is half the maximum imbalance (rounded up)
        return (imbalance + 1) / 2;
    }
}
Python
class Solution:
    def minSwaps(self, s: str) -> int:
        imbalance = 0  # To track the number of swaps needed
        count = 0  # To track current imbalance
        
        for char in s:
            if char == '[':
                count -= 1
            else:  # char is `']'`
                count += 1
                if count > imbalance:
                    imbalance = count
        
        return (imbalance + 1) // 2

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 2 - Greedy

Observations from the Problem:

  • The number of '[' brackets is equal to the number of ']' brackets.
  • Each bracket has a corresponding counterpart in the string.
  • To maintain a balanced string, at any position i:
    • The count of '[' should be at least equal to the count of ']'.
    • If the count of ']' exceeds the count of '[', a swap is needed.

Algorithm:

  1. Use a variable, balance, to track if brackets are balanced at any index:

    • Initialize balance to 0.

  2. For an opening bracket '[', increment balance by one:

    • This anticipates a closing bracket later to balance it. For '[', balance becomes +1.

  3. For a closing bracket ']', decrement balance by one:

    • This balances a previously encountered opening bracket. For ']', balance becomes -1.

        string:    [   [    ]   ] 
  balance:   1   2    1   0   
  		(at last balance is zero which means all elements are matched)

  4. The key moment for swapping occurs when the count of closing brackets exceeds the number of previously seen opening brackets:

    • When balance < 0 or balance == -1, swap the current closing bracket with the first '[' encountered from the end.

    • This adjustment changes the balance to 1, and you can continue searching for closing brackets.

        string:     [      ]       ]          [
  balance :	 (1)    (0)    (-1)  ....  (1)  
  // Swap (-1) with the last (1) to balance it

    • As soon as we swap the brackets, we need to again set balance to 1 as current bracket is opening -> '[' = 1

Lets Do a dry run on string : "[ ] ] ] [ [ ] ["

index:   0  1  2  3  4  5  6  7
string : [  ]  ]  ]  [  [  ]  [
balance: 1  0 -1  .  .  .  .  .
-> swap `']'` at index 2 with first `'['` from last i.e index 7
=> swap = 1 , set balance to 1 

After swapping we continue till end until balance does not become -1. 
If balance = -1, repeat above steps

index:   0  1  2  3  4  5  6  7
string : [  ]  [  ]  [  [  ]  ]
balance: 1  0  1  0  1  2  1  0  
-> This is final value of balance and state string that is balanced

Code

Java
int minSwaps(string s) {
	int n = s.size();
	int balance = 0, swaps = 0, j=n-1;
	char[] arr = s.toCharArray();
	for(int i=0; i<n; i++)
	{
		if(arr[i] == '[') balance++;
		else balance--;

		if(balance < 0)
		{
			while(i<j && arr[j] != '[') j--;
			swap(arr, i, j);
			swaps++;
			balance = 1;
		}
	}
	return swaps;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)