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

给你两个字符串 a 和 b ，二者均由小写字母组成。一步操作中，你可以将 a 或 b 中的 任一字符 改变为 任一小写字母
。

操作的最终目标是满足下列三个条件之一：

a 中的 每个字母 在字母表中 严格小于 b 中的 每个字母 。
b 中的 每个字母 在字母表中 严格小于 a 中的 每个字母 。
a 和 b 都由 同一个 字母组成。

返回达成目标所需的最少操作数。

示例 1：

**输入：** a = "aba", b = "caa"
**输出：** 2
**解释：** 满足每个条件的最佳方案分别是：
1) 将 b 变为 "ccc"，2 次操作，满足 a 中的每个字母都小于 b 中的每个字母；
2) 将 a 变为 "bbb" 并将 b 变为 "aaa"，3 次操作，满足 b 中的每个字母都小于 a 中的每个字母；
3) 将 a 变为 "aaa" 并将 b 变为 "aaa"，2 次操作，满足 a 和 b 由同一个字母组成。
最佳的方案只需要 2 次操作（满足条件 1 或者条件 3）。

示例 2：

**输入：** a = "dabadd", b = "cda"
**输出：** 3
**解释：** 满足条件 1 的最佳方案是将 b 变为 "eee" 。

提示：

1 <= a.length, b.length <= 105
a 和 b 只由小写字母组成

计数 + 枚举

使用 c1 和 c2 对字符串 a 和 b 分别进行词频统计，记字符串 a 和 b 的长度为 n 和 m。

然后枚举字符 i，分别对三种情况的修改次数进行统计：

对应条件 1：目的是要将字符串 a 中所有的字符变得「严格小于」字符 i，将字符串 b 中的所有字符变成「不小于/大于等于」字符 i。
这可以分别统计 a 中大小满足「大于等于」字符 i 的字符数量，以及 b 中大小满足「小于」字符 i 数量，两者之和即是满足该条件的最小修改次数。
注意，当 i = 0（含义为枚举到小写字母 a）时，需要跳过，因为不存在值大小「严格小于」字母 a 的字符，即无法做到将某个字符串替换成所有字符都「严格小于」字母 a；
对应条件 2：与条件 1 同理；
对应条件 3：如果要将两字符的所有字符都变成 i，其中字符串 a 要修改的字符数为 ca = n - c1[i]，字符串 b 要修改的字符数为 cb = m - c2[i]，总修改次数为 ca + cb。

枚举完所有的字符 i 后，统计到的所有修改次数的最小值即是答案。

代码：

[]class Solution {
    public int minCharacters(String a, String b) {
        int n = a.length(), m = b.length(), ans = 0x3f3f3f3f;
        int[] c1 = new int[26], c2 = new int[26];
        for (char c : a.toCharArray()) c1[c - 'a']++;
        for (char c : b.toCharArray()) c2[c - 'a']++;
        for (int i = 0; i < 26 && ans != 0; i++) {
            // 3
            int ca = n - c1[i], cb = m - c2[i];
            ans = Math.min(ans, ca + cb);
            if (i == 0) continue;
            int r1 = 0, r2 = 0;
            // 1
            for (int j = i; j < 26; j++) r1 += c1[j];
            for (int j = 0; j < i; j++) r1 += c2[j];
            // 2
            for (int j = i; j < 26; j++) r2 += c2[j];
            for (int j = 0; j < i; j++) r2 += c1[j];
            ans = Math.min(ans, Math.min(r1, r2));
        }
        return ans;
    }
}

时间复杂度：统计词频的复杂度为 O(n + m)，统计答案的复杂度为 O(C^2)，其中 C = 26 为字符集大小
空间复杂度：O(C)

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你关注我和加入我们的「组队打卡」小群，提供写「证明」&「思路」的高质量题解。

所有题解已经加入刷题指南，欢迎 star 哦 ~