problems/1737.change-minimum-characters-to-satisfy-one-of-three-conditions.md · lonuslan/leetcode

## 题目地址(1737. 满足三条件之一需改变的最少字符数)

https://leetcode-cn.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/

## 题目描述

```
给你两个字符串 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。接下来，我们就可以执行核心的枚举逻辑了。

核心代码:

```python
        # 枚举 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 种可能，因此直接枚举即可。

核心代码:

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

## 关键点

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

## 代码

- 语言支持：Python3

Python3 Code:

```python
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 转化为同一字符的最小操作数。

Python3 Code:

```py
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)$

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)

lonuslan/leetcode

简介

发行版

贡献者

近期动态

lonuslan/leetcode .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

lonuslan/leetcode