# LeetCode 1717. Maximum Score From Removing Substrings

https://leetcode.com/problems/maximum-score-from-removing-substrings/description/

## 題目大意

從字串`s` 中移除 `"ab"` 得 `x` 分、移除 `"ba"` 得 `y` 分
回傳最多可以拿幾分？

## 思考

這題明顯我們可以使用 greedy 的策略
首先要知道移除一次 `"ab"` 或 `"ba"` 誰分數更高
這邊我們換個想法，變成永遠假設移除 `"ab"` 的分數會更高，因此如果 `x < y` 則我們交換得分並反轉 `s`

由於我們的策略已經定好，優先移除 `"ab"` 就成了目標
遇到 `'a'` 我們計數就增加、遇到 `'b'` 我們要檢查一下能不能形成 `"ab"` ，如果可以就移掉並得分；反之， `'b'` 計數增加

如果我們遇到不是 `'a'` 或 `'b'` 的字符，則計算移除 `"ba"` 的得分 (`cnt_a` 跟 `cnt_b` 皆非零時代表雖然沒辦法移除 `"ab"` 但我們還能移除 `"ba"`)
記得要清空計數，這樣才能保證我們假想移除的是子字串

class Solution
{
public:
    int maximumGain(string s, int x, int y)
    {
        if (x < y)
        {
            swap(x, y);
            reverse(s.begin(), s.end());
        }

        int cnt_a = 0, cnt_b = 0, ans = 0;

        for (const char c : s)
        {
            if (c == 'a')
                ++cnt_a;
            else if (c == 'b')
            {
                if (cnt_a > 0)
                {
                    --cnt_a;
                    ans += x;
                }
                else
                    ++cnt_b;
            }
            else
            {
                ans += min(cnt_a, cnt_b) * y;
                cnt_a = cnt_b = 0;
            }
        }

        ans += min(cnt_a, cnt_b) * y;

        return ans;
    }
};