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

题目描述

这是 LeetCode 上的 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 <= 10^5$
• a 和 b 只由小写字母组成

---

计数 + 枚举

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

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

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

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

Java 代码：

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;
    }
}

C++ 代码：

class Solution {
public:
    int minCharacters(string a, string b) {
        int n = a.size(), m = b.size(), ans = 0x3f3f3f3f;
        vector<int> c1(26, 0), c2(26, 0);
        for (char c : a) c1[c - 'a']++;
        for (char c : b) c2[c - 'a']++;
        for (int i = 0; i < 26 && ans != 0; i++) {
            int ca = n - c1[i], cb = m - c2[i];
            ans = min(ans, ca + cb);
            if (i == 0) continue;
            int r1 = 0, r2 = 0;
            for (int j = i; j < 26; j++) r1 += c1[j];
            for (int j = 0; j < i; j++) r1 += c2[j];
            for (int j = i; j < 26; j++) r2 += c2[j];
            for (int j = 0; j < i; j++) r2 += c1[j];
            ans = min(ans, min(r1, r2));
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        n, m, ans = len(a), len(b), 0x3f3f3f3f
        c1, c2 = [0] * 26, [0] * 26
        for c in a:
            c1[ord(c) - ord('a')] += 1
        for c in b:
            c2[ord(c) - ord('a')] += 1
        for i in range(26):
            ca, cb = n - c1[i], m - c2[i]
            ans = min(ans, ca + cb)
            if i == 0:
                continue
            r1, r2 = 0, 0
            for j in range(i, 26):
                r1 += c1[j]
            for j in range(i):
                r1 += c2[j]
            for j in range(i, 26):
                r2 += c2[j]
            for j in range(i):
                r2 += c1[j]
            ans = min(ans, r1, r2)
        return ans

TypeScript 代码：

function minCharacters(a: string, b: string): number {
    let n = a.length, m = b.length, ans = 0x3f3f3f3f;
    const c1 = new Array(26).fill(0), c2 = new Array(26).fill(0);
    for (const c of a) c1[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    for (const c of b) c2[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    for (let i = 0; i < 26 && ans !== 0; i++) {
        const ca = n - c1[i], cb = m - c2[i];
        ans = Math.min(ans, ca + cb);
        if (i === 0) continue;
        let r1 = 0, r2 = 0;
        for (let j = i; j < 26; j++) r1 += c1[j];
        for (let j = 0; j < i; j++) r1 += c2[j];
        for (let j = i; j < 26; j++) r2 += c2[j];
        for (let 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)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1737 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。