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

标签: 哈希表 字符串 计数 前缀和

难度: Medium

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

Submission

运行时间: 99 ms

内存: 16.4 MB

from collections import Counter

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        A = Counter(a)
        B = Counter(b)
        m, n = len(a), len(b)
        ans = m + n
        prevA = prevB = 0
        for i in range(26):
            prevA += A[chr(i + ord("a"))]
            prevB += B[chr(i + ord("a"))]
            if i < 25:
                ans = min(ans, m + n - A[chr(i + ord("a"))] - B[chr(i + ord("a"))], m - prevA + prevB, n + prevA - prevB)
            else:
                ans = min(ans, m + n - A[chr(i + ord("a"))] - B[chr(i + ord("a"))])
        return ans

Explain

题解采用了通过计数的方式来解决问题。首先，通过Counter统计字符串a和b中每个字符的出现次数。然后，遍历从字符'a'到'z'的每个字符，对于每个字符c，计算三种操作的成本：1) 将a中所有字符变为c，b中所有字符变为c；2) 将a中所有字符变得小于c，b中所有字符变得大于c；3) 将b中所有字符变得小于c，a中所有字符变得大于c。利用累积计数（prevA和prevB），可以方便地计算在当前字符c之前或之后，字符串需要变动的字符数。最后，选取三种操作中最小的操作数作为答案。

时间复杂度: O(m+n)

空间复杂度: O(1)

from collections import Counter

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        A = Counter(a)  # 计数a中每个字符的出现次数
        B = Counter(b)  # 计数b中每个字符的出现次数
        m, n = len(a), len(b)
        ans = m + n  # 初始化最少操作数为m+n
        prevA = prevB = 0  # 初始化a和b中小于当前字符的字符数
        for i in range(26):
            char = chr(i + ord('a'))  # 当前字符
            prevA += A[char]  # 更新a中小于等于当前字符的字符总数
            prevB += B[char]  # 更新b中小于等于当前字符的字符总数
            if i < 25:  # 最后一个字符无需比较
                ans = min(ans, m + n - A[char] - B[char], m - prevA + prevB, n + prevA - prevB)  # 更新最小操作数
            else:
                ans = min(ans, m + n - A[char] - B[char])  # 最后一个字符只考虑变为同一个字符的情况
        return ans  # 返回最小操作数

Explore

初始化操作数为字符串a和b的长度之和（m + n）是因为这代表了将a和b中的每个字符都改变为另一个完全不同的字符的最极端情况。这样的初始化提供了一个上限，确保我们在后续计算中，考虑各种可能的字符变换操作时，能找到一个真实的、更小的最小操作数。

在此计算方式中，m - prevA 表示将a中所有大于等于字符c的字符变为小于c的字符所需的最少变动次数，因为prevA是a中小于等于c的字符的累积计数，所以m - prevA就是剩余需要变动的字符数。同理，prevB表示b中小于等于c的字符数，因此需要将这些字符变为大于c的字符，直接使用prevB即可。因此，总的操作次数为将a中的一部分字符减小，和将b中的一部分字符增大，即m - prevA + prevB。

因为字符z是字母表中的最后一个字符，不存在比z更大的字符。因此，在考虑将a中的字符全部变小于b或b中的字符全部变小于a的情况时，不可能实现a中的字符全小于z或b中的字符全小于z的条件。所以，对于字符z，只需要考虑将a和b中的所有字符都变为z的情况，这是唯一可行的操作。

累积计数prevA和prevB通过记录到当前字符为止，在a和b中小于等于当前字符的字符的总数，帮助快速计算不同变换操作所需的字符数。这种方法避免了对每个可能的字符变换重新遍历整个a或b字符串来计数，从而大大减少了计算的复杂度和执行时间。通过累积计数，我们可以直接利用已有的统计信息，快速得到任何字符c之前或之后的字符变动需求，从而实现高效的最优解搜索。