Minimum Swaps for Bracket Balancing

December 30, 2021

Minimum Swaps for Bracket Balancing

In Minimum Swaps for Bracket Balancing Problem, we are given a bracket sequence and we have to make the sequence regular by swapping brackets. The problem can be optimally solved using a greedy algorithm. In this article, we will provide a C++ solution with an explanation.

Minimum Swaps for Bracket Balancing Problem Desciption

Minimum Swaps for Bracket Balancing Problem Description

Given a string consisting of left (‘[‘) & right (‘]’) brackets. The string has equal number of both left and right brackets. You can swap only adjacent brackets at a time. You can perform this operation any number of times. Output the minimum number of operations required to make the sequence regular.

Input

  • Single line input – the input string.

Output

  • The minimum number of operations required.

Problem Solution

The problem can be optimally solved using a greedy algorithm. We know in a regular bracket sequence, the number of left brackets (‘[‘) is always greater than or equal to any prefix of the sequence. So whenever we find a prefix with more number of right brackets than left ones, we move the right bracket to the first left bracket after this position by swapping adjacent brackets.

Steps –

  • Create a vector to store positions of left brackets (‘[‘). This will be used to get positions of the next left brackets when we have more right brackets in a sequence.
  • Create a variable count to check the correctness of a prefix. Iterate over the string and increment count if we encounter a left bracket and decrement count if we encounter a right bracket.
  • If at any time count becomes negative swap the current bracket with the nearest next right bracket and count the number of steps.

To find the next position of the left bracket we can either iterate over the string or use a vector and store positions of left brackets. The vector will be given the nearest next position in O(1) by maintaining a position index pIdx which always points to the next left bracket.

Time Complexity – O(n)

Space Complexity – O(n)

Code

#include <bits/stdc++.h>
using namespace std;
int countSwap(string s)
{
    vector<int> position;

    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == ‘[‘)
            position.push_back(i);
    }

    int ct = 0, pIdx = 0, sum = 0;

    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == ‘[‘)
        {
            ct++;
            pIdx++;
        }
        else
        {
            ct–;
        }

        if (ct < 0)
        {
            sum += position[pIdx] – i;
            swap(s[i], s[position[pIdx]]);
            pIdx++;
            ct = 1;
        }
    }

    return sum;
}
int main()
{
    int t;
    cin >> t;
    while (t–)
    {
        string s;
        cin >> s;
        cout << “Number of swaps = “ << countSwap(s) << endl;
    }

    return 0;
}

Output

2
[]]][[
Number of swaps = 3
[][][]
Number of swaps = 0