Leetcode 1963. Minimum number of swaps to balance strings (learning)

Give you a string s , Subscript from 0 Start , And the length is even n . character string just from n / 2 An open bracket ‘[’ and n / 2 Closed parentheses ‘]’ form .

Only a string that satisfies all of the following conditions can be called Balanced string ：

• The string is an empty string , perhaps
• Strings can be written as AB , among A and B All are Balanced string , perhaps
• The string can be written as [C] , among C It's a Balanced string .

You can exchange arbitrarily The parentheses corresponding to the two subscripts arbitrarily frequency .

Return to make s become Balanced string The required Minimum Number of exchanges .

Example 1：

 Input ：s = "][]["
 Output ：1
 explain ： Swap subscripts  0  And subscripts  3  Corresponding parentheses , You can make a string into a balanced string .
 The final string becomes  "[[]]" .

Example 2：

 Input ：s = "]]][[["
 Output ：2
 explain ： Do the following to make the string balanced ：
-  Swap subscripts  0  And subscripts  4  Corresponding parentheses ,s = "[]][][" .
-  Swap subscripts  1  And subscripts  5  Corresponding parentheses ,s = "[[][]]" .
 The final string becomes  "[[][]]" .

Example 3：

 Input ：s = "[]"
 Output ：0
 explain ： This string is already a balanced string .
 

Tips ：

• n == s.length
• 2 <= n <= 106
• n For the even
• s[i] by ’[’ or ‘]’
• Open bracket ‘[’ The number is n / 2 , close-quote ‘]’ The number of n / 2

Netizen code
Code：

class Solution {
    
public:
    int minSwaps(string s) {
    
        stack<char> stk;
        for (char c : s) {
    
            if (c == ']' && !stk.empty() && stk.top() == '[') {
    
                stk.pop();
            } 
            else {
    
                stk.push(c);
            }
        }
        return (stk.size() / 2 + 1) / 2;;
    }
};