Find Minimum Swaps required for Bracket Balancing

Reading time: 20 minutes

Given a string of 2N characters consisting of N '[' brackets and N ']' brackets, our target is to find the minimum number of swaps required to make the set of brackets balanced.

We will solve this in two approaches:

• Naive approach O(N^2) time
• Efficient approach O(N) time

Background on the problem statement

A bracket is considered to be any one of the following characters:(,),{,},[,or].
Two brackets are said to be matched pair if the opening bracket(i.e., (, [, or {) occurs to the left of a closing bracket(i.e., ),] or }) of the exact same type. There are three types of matched pairs of bracket: [],{}, and ().

A matching pair of brackets is not balanced if the set of brackets it encloses are not matched. For example, {[(])} is not balanced because the contents in between { and } are not balanced. The pair of square brackets encloses a single, unbalanced opening bracket, (, and the pair of paranthesis encloses a single, unbalanced closing sqaure bracket, ].

By this logic, we say a sequence of brackets is balanced if the following conditions are met:

• It contains no unmatched brackets.
• The subset of brackets enclosed within the confines of a matched pair of brackets is also a matched pair of brackets.

Examples of balanced brackets:

[{([])}]
[()]{}

Examples of unbalanced brackets:

{([)}] 
([]}
[)
)[{}](

Question

You are given a string of 2N characters consisting of N '[' brackets and N ']' brackets. Our target is to find the minimum number of swaps required to make the set of brackets balanced.

Examples:

Input:[]][][
Output: 2
First Swap: Position 3 and 4
[][]][
Second swap: Position 5 and 6
[][][]

Another example:

Input: [[][]]
Output: 0
String is already balanced.

Naive Algorithm O(N^2)

The steps involved in the naive approach are:

• Initialize sum=0 where sum stores result.

• Go through the string maintaining a count of the number of '[' brackets encountered. Reduce this count when we encounter a ']' character.

• If the count hits negative, then we must start balancing the string.

• Let index 'i' represents the position we are at. We now move forward to the next '[' at index j. Increase sum by j-i.

• Move the '[' at position j, to position i and shift all other characters to the right.

• Set the count back to 0 and continue traversing the string. At the end 'sum' will have the required value.

Optimized Approach O(N)

The steps and key idea of solving this in linear time are:

• We can initially go through the string and store the positions of '[' in a vector say 'pos'.

• Initialize 'p' to 0. We shall use p to traverse the vector 'pos'.

• Similar to the naive approach, we maintain a count of encountered '[' brackets. When we encounter a '[' we increase the count, and increase 'p' by 1. When we encounter a ']' we decrease the count.

• If the count ever goes negative, this mean we must start swapping. The element pos[p] tells us the index of the next '['. We increase the sum by pos[p]-i, where i is the current index. We can swap the elements in the current index and pos[p] and reset count to 0.

This way we can find the minimum number of swaps required in linear time O(N)

Note that this optimized approach requires O(N) memory while the naive approach required constant O(1) memory. If memory is a constraint, the slower naive approach may be used.

Implementation

     #include <bits/stdc++.h> 
     using namespace std; 

        // Function to calculate swaps required 
        long swapCount(string s) 
        { 
            // Keep track of '[' 
            vector<int> pos; 
            for (int i = 0; i < s.length(); ++i) 
                if (s[i] == '[') 
                    pos.push_back(i); 

            int count = 0; // To count number of encountered '[' 
            int p = 0;  // To track position of next '[' in pos 
            long sum = 0; // To store result
            for (int i = 0; i < s.length(); ++i) 
            { 
                // Increment count and move p to next position 
                if (s[i] == '[') 
                { 
                    ++count; 
                    ++p; 
                } 
                else if (s[i] == ']') 
                    --count;
                // We have encountered an unbalanced part of string 
                if (count < 0) 
                { 
                    // Increment sum by number of swaps required 
                    // i.e. position of next '[' - current position 
                    sum += pos[p] - i; 
                    swap(s[i], s[pos[p]]); 
                    ++p; 

                    // Reset count to 1 
                    count = 1; 
                } 
            } 
            return sum; 
        } 

        // Driver code 
        int main() 
        { 
            string s = "[]][]["; 
            cout << swapCount(s) << "\n"; 

            s = "[[][]]"; 
            cout << swapCount(s) << "\n"; 
            return 0; 
        } 

Complexity

Naive Approach-
Time Complexity- O(n^2)
Space Complexity- O(1)

Optimized Approach-
Time Complexity- O(n)
Space Complexity- O(n)