Strings: Minimum swaps required for bracket balancing

Problem Statement:

You are given a string with 2N characters consisting of equally “[” and “]” brackets.

They are unbalanced, you need to find the minimum swaps required for them to make balanced.

Example

Input : []][][
Output : 2
Swap position 3 and 4 [][]][
Then swap position 5 and 6 [][][]

Solution

The solution is very simple.

We take another vector that will hold the positions of ‘[‘.

Then we take a counter “p” that will traverse the vector.

We will maintain a count of ‘[‘ and increase ‘p’ by 1.

When we encounter a ‘]’ we decrease the count.

If it goes negative we shall start swapping.

Time Complexity O(n)
Space Complexity O(n)

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <queue>
#include <sstream> 

using namespace std;

long count_swaps_required(string str) 
{ 
   vector<int> pos; 
   for (int i = 0; i < str.length(); ++i)
   { 
       if (str[i] == '[')
       { 
           pos.push_back(i); 
       }
   }

   int count = 0; // required count number of encountered '[' 
   int p = 0;  // used to track position of next '[' in pos 
   long result = 0; //used to store result

   for (int i = 0; i < str.length(); ++i) 
   { 
       // When '[' is encountered, 
      //   increment count and move p to next position 

       if (str[i] == '[') 
       { 
           ++count; 
           ++p; 
       } 
       else if (str[i] == ']') 
           --count;

       if (count < 0) 
       { 
           result += pos[p] - i; 
           swap(str[i], str[pos[p]]); 
           ++p; 

           // reset count to 1 
           count = 1; 
       } 
   } 
   return result; 
} 

int main() 
{ 
   string str = "[]][]["; 
   cout << "The number of swaps required are = " <<count_swaps_required(str) << endl; 

   return 0; 
} 

Output:

The number of swaps required are = 2