1737. 满足三条件之一需改变的最少字符数

地址：

1737. 满足三条件之一需改变的最少字符数

状态：AC

代码：
以示例 2 中 a = “dabadd”, b = “cda” 为例。首先计算出两个字符串中字母的次数，如图所示。为了省事只列出字母a~f，

满足条件一，等同于要让a字符串所有出现次数大于0的字母统统小于b字符串出现次数大于0的字母，条件二反之。
为达成这个目的，要么把灰色区域的字母次数全改为0，叠加至蓝色区域；要么就得把蓝色区域的字母次数全改为0，叠加至灰色区域。依次扫描字母a~y，灰色或蓝色区域的数字之和即为可能的答案（修改的字母数量）取值，枚举灰色和蓝色区域的值，求最小值。这个枚举的值很容易就能通过前缀和、后缀和算出来。

上下两张图对应的分别是扫描至字符 a 和字符 c 时的情况。

注意最后一个字符 z 不能扫描，不满足上述两个条件。

同时在扫描25个字符的过程中我们还可以顺便计算第三种情况，也就是把两个字符串全改成同一个字符。它的取值是 a.size() + b.size() - 当前字符在a、b出现的次数总和。

不要忘了最后要算一下全改成字符 z 的情况。

class Solution {
public:
    int minCharacters(string a, string b) {
        vector<int> acnt(26, 0);
        vector<int> bcnt(26, 0);
        int an = a.size(), bn = b.size();
        for (char c : a) acnt[c-'a']++;
        for (char c : b) bcnt[c-'a']++;
        int ans = INT_MAX, asum = 0, bsum = 0;
        for (int i = 0; i < 25; i++) {
            asum += acnt[i];
            bsum += bcnt[i];
            ans = min(min(ans, an-acnt[i]+bn-bcnt[i]), min(an-asum+bsum, bn-bsum+asum));
        }
        ans = min(ans, an-acnt[25]+bn-bcnt[25]);
        return ans;
    }
};