# 1737. 满足三条件之一需改变的最少字符数
### 题目地址(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 只由小写字母组成
```
### 前置知识
* 计数
* 枚举
### 公司
* 暂无
### 思路
三个条件中，**前两个条件其实是一样的**，因为如果你会了其中一个，那么你只需要将 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 题解仓库： 。 目前已经 40K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1737.change-minimum-characters-to-satisfy-one-of-three-conditions.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.