5840. Minimum Number of Swaps to Make the String Balanced

tag: stack, greedy

Description

Solution

In each switch, brackets are reduced mostly 2, at least 1.

//Just swap the first dismatched ] with second dismatched [
2 for: ]]] [[[ -> []] [][. 
1 for just 1 pair left, switch them then all done

Code

class Solution {
public:
    int minSwaps(string s) {
        //只要[的右边有对应个数个]即可
        stack<int> stk;
        int res = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '['){
                stk.push(i);
            }else{
                if(stk.empty())
                    res++;
                else
                    stk.pop();
            }
        }
        return res - res/2;
    }
};