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

地址;

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

状态：未AC

代码：贪心

【无需额外空间】贪心算法

class Solution {
public:
    int maximumGain(string s, int x, int y) {
        int n = s.length();
        if (x < y) {
            swap(x, y);
            for (int i = 0; i < n; i++) {
                if (s[i] == 'a') s[i] = 'b';
                else if (s[i] == 'b') s[i] = 'a';
            }
        }
        int ret = 0;
        int i = 0;
        while (i < n) {
            while (i < n && s[i] != 'a' && s[i] != 'b') i++;
            int ca = 0, cb = 0;
            while (i < n && (s[i] == 'a' || s[i] == 'b')) {
                if (s[i] == 'a') {
                    ca++;
                } else {
                    if (ca > 0) {
                        ca--;
                        ret += x;
                    } else {
                        cb++;
                    }
                }
                i++;
            }
            ret += min(ca, cb) * y;
        }
        return ret;
    }
};

思路相同，没有字符串转换

/*
 * ab -> x
 * ba -> y
 * 贪心的先去构建价值高的情况甲的，这样子剩下就只有可能情况乙
 */
class Solution {
public:
    int maximumGain(string s, int x, int y) {
        int a=0,b=0;
        s+='-';
        int ans=0;
        for (char i:s) {
            if (i=='a' || i=='b') {
                if (i=='a') {
                    a++;
                } else {
                    b++;
                }
                if (x>=y && i=='b' && a>0) {
                    a--;
                    b--;
                    ans+=x;
                } else if (x<=y && i=='a' && b>0) {
                    a--;
                    b--;
                    ans+=y;
                }
            } else {
                int cho=min(a,b);
                int val=min(x,y);
                ans+=cho*val;
                a=b=0;
            }
        }
        return ans;
    }
};