Description

Submission

class Solution {
public:
    int minSwaps(string s) {
        int curLeft = 0;
        int permanentRight = 0;

        for(char ch: s) {
            if(ch == '[') {
                ++curLeft;
            } else {
                --curLeft;
            }

            if(curLeft < 0) {
                curLeft = 0;
                ++permanentRight;
            }
        }

        return (permanentRight + 1) / 2;
    }
};

Submission 220111

class Solution {
public:
    int minSwaps(string s) {
        int ret = 0;   
        int left = 0;

        vector<int> rights;

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

        for(int i = 0; i < s.length(); ++i) {
            char ch = s[i];
            if(ch == '[') ++left;
            else {
                if(left == 0) {
                    ++ret;
                    ++left;
                    swap(s[i], s[rights.back()]);
                    rights.pop_back();
                } else {
                    --left;
                }
            }
        }

        return ret;
    }
};

// ][][