Problem 24: Minimum Swaps for Bracket Sequence

Problem Statement: Given a string consisting of only '[' and ']', determine the minimum number of adjacent swaps required to balance the bracket sequence. It is guaranteed that a balanced arrangement exists.

Input

A single line containing a string of '[' and ']'.

Output

Print the minimum number of swaps needed.

Examples


Input:
]][][][[

Output:
2

Solution Explanation

Method 1: Use a greedy approach by tracking the imbalance and swapping when the balance becomes negative. Method 2: Record the positions of the '[' brackets and calculate the total distance between their current positions and the positions of the balanced configuration.

Solution in C++


#include 
#include 
#include 
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s; cin >> s;
    int n = s.size();
    vector pos;
    for (int i = 0; i < n; i++) {
        if(s[i]=='[') pos.push_back(i);
    }
    int count = 0, p = 0, ans = 0;
    for(int i = 0; i < n; i++){
        if(s[i]=='[') {
            count++;
            p++;
        } else {
            count--;
        }
        if(count < 0){
            ans += pos[p] - i;
            swap(s[i], s[pos[p]]);
            p++;
            count = 1;
        }
    }
    cout << ans << "
";
    return 0;
}