文章目錄

• • 題目
  • 題目鏈接

題目

樣例

字符串可以分成很多段，[ ab的組合]、其他字母、[ab的組合]、其他字母這樣很多段，樣例就是 cd[b]c[bbaaabab]可以拆成ab的組合和其他字母。

對于某一段[ab的組合]，需要計數(shù)a和b的個數(shù)：分別記為A和B。比如[abbaaba]其中a的個數(shù)A=4，b的個數(shù)B=3. 這一段可以操作的數(shù)量是min(A,B)=3次，這里的每次操作消耗掉一個a和一個b。而且只要有相鄰的a和b就可以操作。

這里我們假定ab的得分大于等于ba的得分，即x≥y。（可以省去一半的思考時間），那么想要得分最大，就需要 刪除ab的操作盡可能多。

最多可以刪除多少個ab呢?

可以貪心來做。某個位置的a，能否和b配對，取決于其后面是否有b。如果和b相鄰那么自然可以配對。我們從后往前遍歷，計數(shù)b的數(shù)量（相當(dāng)于放在后備箱），往前掃的過程中每遇到一個a，就從后備箱拿出一個b，計數(shù)器減1.代表成功配對1個ab。如果后備箱中沒有b，這個a就不能配成ab。

這樣遍歷完之后，最大的ab個數(shù)就確定了，而總的操作次數(shù)是min(A,B)，則操作ba的個數(shù)就是min(A,B)-ab個數(shù).然后分別乘以得分x和y即為最大得分。

ac代碼

class Solution {
public:
    int maximumGain(string s, int x, int y) {
        //假定x≥y
        if(x<y){
            swap(x,y);
            for(auto& c:s){
                if(c=='a') c='b';
                else if(c=='b') c='a';
            }
        }
       
        int res=0;

        for(int i=0; i< s.size();i  ){ //用i和j來指明某一段[i,j)左閉右開
            if(s[i]!='a' && s[i]!='b') continue;

            int j=i;
            while(j<s.size() && ( s[j]=='a'|| s[j]=='b')) j  ;//執(zhí)行這一步之后j一定在i后面

            int a=0,b=0,c=0, remain=0;//remain表示后備箱中b的數(shù)量
            //c表示找出來ab的數(shù)量
            for(int k = j-1; k>= i; k --){ //具體的一段的處理
                if(s[k]=='a'){
                    a  ;
                    if(remain) { //后備箱中還有b
                        remain--;
                        c  ;
                    }
                }else {//s[k]=='b'
                    b  ;
                    remain  ;
                }
            }
            res =c*x  (min(a,b)-c)*y;//加號后面表示"ba"的數(shù)量×分?jǐn)?shù)y
             i=j; //這一段結(jié)束，遍歷下一段
            
        }
        return res;


    }
};

題目鏈接

Leetcode5634. 刪除子字符串的最大得分