Leetcode5634. 删除子字符串的最大得分[C 题解]：贪心

文章目录

• • 题目
  • 题目链接

题目

样例

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

对于某一段[ab的组合]，需要计数a和b的个数：分别记为A和B。比如[abbaaba]其中a的个数A=4，b的个数B=3. 这一段可以操作的数量是min(A,B)=3次，这里的每次操作消耗掉一个a和一个b。而且只要有相邻的a和b就可以操作。

这里我们假定ab的得分大于等于ba的得分，即x≥y。（可以省去一半的思考时间），那么想要得分最大，就需要 删除ab的操作尽可能多。

最多可以删除多少个ab呢?

可以贪心来做。某个位置的a，能否和b配对，取决于其后面是否有b。如果和b相邻那么自然可以配对。我们从后往前遍历，计数b的数量（相当于放在后备箱），往前扫的过程中每遇到一个a，就从后备箱拿出一个b，计数器减1.代表成功配对1个ab。如果后备箱中没有b，这个a就不能配成ab。

这样遍历完之后，最大的ab个数就确定了，而总的操作次数是min(A,B)，则操作ba的个数就是min(A,B)-ab个数.然后分别乘以得分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  ;//执行这一步之后j一定在i后面

            int a=0,b=0,c=0, remain=0;//remain表示后备箱中b的数量
            //c表示找出来ab的数量
            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"的数量×分数y
             i=j; //这一段结束，遍历下一段
            
        }
        return res;


    }
};

题目链接

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

来源：https://www./content-1-816401.html