Minimum number of swaps for bracket balancing in C++

Swaps for bracket balancing

Today we will be learning how to swaps for bracket balancing using minimum operations.

Lets understand this with the help of example.

  • Input : [[][]]
  • Output : 0

Here the number of opening brackets and the number of closing brackets are the same also its balanced

swaps for bracket balancing
  • We are given a string of 2N characters  (even) consisting of N ‘[‘ brackets and N ‘]’ brackets, A string is considered balanced if it can be represented in the for S2[S1] where S1 and S2 are balanced strings.
  • Set sum to 0, where sum stores the result. Continue through the string, keeping track of the number of ‘[‘ brackets encountered.
  • When we come across a ‘]’ character, we should reduce this count. If the count falls below zero, we must begin balancing the string. Let index I represent our current position. We now proceed to the next ‘[‘ at index j.
  • Increase the total by j – i. Move the ‘[‘ at position j, to position i, and shift all other characters to the right. Return the count to 0 and proceed with the string traversal. ‘sum’ will have the required value at the end.

Swaps for bracket balancing C++ Code

Run
#include <iostream> 
#include <vector> 
#include <algorithm> 

using namespace std;
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;
   int p = 0;
   long sum = 0;

   for (int i = 0; i < s.length (); ++i)
   {
    if (s[i] == '[')
    {
      ++count;
      ++p; 
    }
  else if (s[i] == ']')
    --count;

  if (count < 0)
  {

   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) << " ";
  s = "[[][]]";
  cout << swapCount (s) << " ";

  return 0;
}
Minimum number of operations required is 3