(nice!!!)(LeetCode 每日一题) 1717. 删除子字符串的最大得分 (贪心)

题目：1717. 删除子字符串的最大得分

思路：贪心，时间复杂度0(n)。

非a/b的字符，都可视为分隔符，将字符串s分割为多个只有ab的子串。然后在子串里，优先满足ab的情况(假设ab的分＞ba的分)，细节看注释。

C++版本：

class Solution {
public:
    int maximumGain(string s, int x, int y) {
    	// 优先处理分数大的情况，
        char a='a',b='b';
        if(x<y){
            swap(a,b);
            swap(x,y);
        }
        // sum是答案
        // cta是当前子串里a字符的数量，ctb是当前子串里b字符的数量
        int sum=0,cta=0,ctb=0;
        for(auto c:s){
        	// 优先判断ab的情况，所以遇到a字符时，cta++
            if(c==a){
                cta++;
            }else if(c==b){
            	//遇到b字符时，判断前面是否有a
                if(cta>0){
                    cta--;
                    sum+=x;
                }else{
                	//无a就记录b字符的数量，用于后面ba的情况
                    ctb++;
                }
            }else{
            	//遇到非a、b的字符，那么这一段子串处理就结束了
            	// ab的情况，前面都已经处理了，这里再处理ba的情况
                sum+=y*min(cta,ctb);
                cta=0;
                ctb=0;
            }
        }
        // 处理边界情况
        sum+=y*min(cta,ctb);
        return sum;
    }
};

JAVA版本：

class Solution {
    public int maximumGain(String s, int x, int y) {
        char a='a',b='b';
        if(x<y){
            char t=a;
            a=b;
            b=t;
            int c=x;
            x=y;
            y=c;
        }
        int sum=0,cta=0,ctb=0;
        for(var c:s.toCharArray()){
            if(c==a){
                cta++;
            }else if(c==b){
                if(cta>0){
                    cta--;
                    sum+=x;
                }else{
                    ctb++;
                }
            }else{
                sum+=Math.min(cta,ctb)*y;
                cta=0;
                ctb=0;
            }
        }
        sum+=Math.min(cta,ctb)*y;
        return sum;
    }
}

GO版本：

func maximumGain(s string, x int, y int) int {
    a,b:='a','b'
    if x<y {
        x,y=y,x
        a,b=b,a
    }
    sum,cta,ctb:=0,0,0
    for _,c:=range s {
        if c==a {
            cta++
        }else if c==b {
            if cta>0 {
                cta--
                sum+=x
            }else {
                ctb++
            }
        }else{
            sum+=min(cta,ctb)*y
            cta=0
            ctb=0
        }
    }
    sum+=min(cta,ctb)*y
    return sum
}