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

Question

给你两个字符串 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 只由小写字母组成

前置知识

• 计数
• 枚举

思路

三个条件中，前两个条件其实是一样的，因为如果你会了其中一个，那么你只需要将 A 和 B 交换位置就可以解出另外一个了。

对于前两个条件来说，我们可以枚举所有可能。以条件一 A 中的 每个字母 在字母表中 严格小于 B 中的 每个字母 为例。我们要做的就是枚举所有可能的 A 的最大字母 和 B 的最小字母（其中 A 的最大字母保证严格小于 B 的最大字母），并计算操作数，最后取最小值即可。

代码上，我们需要先统计 A 和 B 的字符出现次数信息，不妨分别记为 counter_A 和 counter_B。接下来，我们就可以执行核心的枚举逻辑了。

核心代码:

        # 枚举 A 的最大字母
        for i in range(1, 26):
            t = 0
            # A 中大于等于 i 的所有字符都需要进行一次操作
            for j in range(i, 26):
                t += counter_A[j]
            # B 中小于 i 的所有字符都需要进行一次操作
            for j in range(i):
                t += counter_B[j]
            # 枚举的所有情况中取最小的
            ans = min(ans, t)

而对于第三个条件，则比较简单，我们只需要将 A 和 B 改为同一个字母，并计算出操作数，取最小值即可。我们可能修改成的字母一共只有 26 种可能，因此直接枚举即可。

核心代码:

for i in range(26):
     ans = min(ans, len(A) + len(B) - counter_A[i] - counter_B[i])

关键点

• 使用一个长度为 26 的数组计数不仅性能比哈希表好，并且在这里代码书写会更简单

代码

• 语言支持：Python3

class Solution:
    def minCharacters(self, A: str, B: str) -> int:
        counter_A = [0] * 26
        counter_B = [0] * 26
        for a in A:
            counter_A[ord(a) - ord('a')] += 1
        for b in B:
            counter_B[ord(b) - ord('a')] += 1
        ans = len(A) + len(B)
        for i in range(26):
            ans = min(ans, len(A) + len(B) - counter_A[i] - counter_B[i])
        for i in range(1, 26):
            t = 0
            for j in range(i, 26):
                t += counter_A[j]
            for j in range(i):
                t += counter_B[j]
            ans = min(ans, t)
        for i in range(1, 26):
            t = 0
            for j in range(i, 26):
                t += counter_B[j]
            for j in range(i):
                t += counter_A[j]
            ans = min(ans, t)
        return ans

我们也可以将操作封装成函数方便理解。其中：

• greater_cost(a, b) 表示 a 中严格大于 b 的最小操作数。
• equal_cost(a, b) 表示将 a 和 b 转化为同一字符的最小操作数。

class Solution:
    def minCharacters(self, A: str, B: str) -> int:
        ca = collections.Counter(A)
        cb = collections.Counter(B)
        # ca 中严格大于 cb 的最小操作数
        def greater_cost(ca, cb):
            ans = float("inf")
            # 枚举 ca 中的最小值
            for i in range(1, 26):
                count = 0
                # 将 ca 中小于最小值的都进行一次操作
                for j in range(i):
                    count += ca[chr(97 + j)]
                # 将 cb 中大于等于最小值的都进行一次操作（注意这里的等号）
                for j in range(i, 26):
                    count += cb[chr(97 + j)]
                ans = min(ans, count)
            return ans

        def equal_cost(ca, cb):
            ans = float("inf")
            for i in range(26):
                ans = min(ans, len(A) + len(B) - ca[chr(97 + i)] - cb[chr(97 + i)])
            return ans

        return min(greater_cost(ca, cb), greater_cost(cb, ca), equal_cost(ca, cb))

复杂度分析

令 m, n 分别为数组 A 和数组 B 的长度。

• 时间复杂度：$O(m + n)$
• 空间复杂度：$O(26)$