Minimum number of swaps for bracket balancing in C++

June 17, 2022

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

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  
#include  
#include  

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

Note Time Complexity = O(N^2) Extra Space = O(1)

Swaps for bracket balancing in JAVA Code

Run

import java.util.*;
class Main {
    static int swapsMin(String s) {
        Stack stack = new Stack<>();
        for (char ch : s.toCharArray()) {
            if (ch == '[')
                stack.push(ch);
            else {
                if ((!stack.isEmpty()) && ((char)stack.peek()=='['))
                    stack.pop();
                else
                    stack.push(ch);
            }
        }
        int u = stack.size() / 2; 
        return (u + 1) / 2;
    }

    public static void main(String[] args) {
        String s = "[[][]]";
        System.out.println("The number of swaps needed are: "+swapsMin(s));
    }
}

The number of swaps needed are: 0