You are given a 0-indexed string s of even length n. The string consists of exactly n / 2 opening brackets '[' and n / 2 closing brackets ']'.

A string is called balanced if and only if:


	It is the empty string, or
	It can be written as AB, where both A and B are balanced strings, or
	It can be written as [C], where C is a balanced string.


You may swap the brackets at any two indices any number of times.

Return the minimum number of swaps to make s balanced.

&nbsp;
Example 1:

Input: s = "][]["
Output: 1
Explanation: You can make the string balanced by swapping index 0 with index 3.
The resulting string is "[[]]".


Example 2:

Input: s = "]]][[["
Output: 2
Explanation: You can do the following to make the string balanced:
- Swap index 0 with index 4. s = "[]][][".
- Swap index 1 with index 5. s = "[[][]]".
The resulting string is "[[][]]".


Example 3:

Input: s = "[]"
Output: 0
Explanation: The string is already balanced.


&nbsp;
Constraints:


	n == s.length
	2 &lt;= n &lt;= 106
	n is even.
	s[i] is either '[' or ']'.
	The number of opening brackets '[' equals n / 2, and the number of closing brackets ']' equals n / 2.


class Solution:
    def minSwaps(self, s: str) -> int:
        res, bal = 0, 0
        for ch in s:
            bal += 1 if ch == '[' else -1
            if bal == -1:
                res += 1
                bal = 1
        return res
class Solution {
    public int minSwaps(String s) {
        // remove the balanced part from the given string
        Stack<Character> stack = new Stack<>();
        for(char ch : s.toCharArray()) {
            if(ch == '[')
                stack.push(ch);
            else {
                if(!stack.isEmpty() && stack.peek() == '[')
                    stack.pop();
                else
                    stack.push(ch);
            }
        }
        int unb = stack.size()/2; // # of open or close bracket
        return (unb+1)/2;
    }
}
class Solution {
public:
    int minSwaps(string s) {
        int ans=0;
        stack<char> stack;
        for(int i=0;i<s.length();i++){
            if(s[i]=='['){
                stack.push(s[i]);
            }
            if(s[i]==']' && stack.size()!=0 && stack.top()=='['){
                stack.pop();
            }

        }

        ans=stack.size();
        if(ans%2==0)
            return ans/2;
        else
            return (ans+1)/2;

    }
};
/**
 * @param {string} s
 * @return {number}
 */
var minSwaps = function(s) {
    let stk = []
    for(let c of s){
        if(stk && c == ']')    stk.pop()
        else if(c == '[')   stk.push(c)
    }
    return (stk.length) / 2
};
Minimum Number of Swaps to Make the String Balanced