1963. Minimum Number of Swaps to Make the String Balanced

周賽復盤

這題有點難, 雖然我不知道寫周賽的當下要怎麼想到

首先我們看到

]]][[[

我們可以去想, 倘若為[就+1, ]就-1, 所以可以把上面這段改成

[-1, -2, -3, -2, -1, 0]

所以可以看到最差最差為-3, 而可以發現假設要達成balance的string

必須整個數列的數字必須都是正整數或零

所以假設我們移動最左邊的],以及最右邊的[

可以看到

[ ]][[ ]
[1,0,-1, 0,1, 0]

剛剛原本最差的-3, 瞬間被加2了

所以我們可以得知, 最少要Swap的次數為最差的值除以2, 取floor, 就可以在最小限度內讓字串變得balance

時間複雜度為O(n), 但我個人覺得當下真的很難想到

真不知道周賽當下可以寫過的人怎麼想的

class Solution {
public:
int minSwaps(string s) {
        int min_neg = 0;
        int sum = 0;
        for(auto c:s){
            if(c == '['){
                sum++;
            }else{
                sum--;
            }
            min_neg = min(sum, min_neg);
        }
        if(min_neg == 0) return 0;
        return ceil(-(min_neg / 2.0));
    }
};