第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
1737. 满足三条件之一需改变的最少字符数

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

题目描述

1
给你两个字符串 a 和 b ,二者均由小写字母组成。一步操作中,你可以将 a 或 b 中的 任一字符 改变为 任一小写字母 。
2
3
操作的最终目标是满足下列三个条件 之一 :
4
5
a 中的 每个字母 在字母表中 严格小于 b 中的 每个字母 。
6
b 中的 每个字母 在字母表中 严格小于 a 中的 每个字母 。
7
a 和 b 都 由 同一个 字母组成。
8
返回达成目标所需的 最少 操作数。
9
10
11
12
示例 1:
13
14
输入:a = "aba", b = "caa"
15
输出:2
16
解释:满足每个条件的最佳方案分别是:
17
1) 将 b 变为 "ccc",2 次操作,满足 a 中的每个字母都小于 b 中的每个字母;
18
2) 将 a 变为 "bbb" 并将 b 变为 "aaa",3 次操作,满足 b 中的每个字母都小于 a 中的每个字母;
19
3) 将 a 变为 "aaa" 并将 b 变为 "aaa",2 次操作,满足 a 和 b 由同一个字母组成。
20
最佳的方案只需要 2 次操作(满足条件 1 或者条件 3)。
21
示例 2:
22
23
输入:a = "dabadd", b = "cda"
24
输出:3
25
解释:满足条件 1 的最佳方案是将 b 变为 "eee" 。
26
27
28
提示:
29
30
1 <= a.length, b.length <= 105
31
a 和 b 只由小写字母组成
Copied!

前置知识

  • 计数
  • 枚举

公司

  • 暂无

思路

三个条件中,前两个条件其实是一样的,因为如果你会了其中一个,那么你只需要将 A 和 B 交换位置就可以解出另外一个了。
对于前两个条件来说,我们可以枚举所有可能。以条件一 A 中的 每个字母 在字母表中 严格小于 B 中的 每个字母 为例。我们要做的就是枚举所有可能的 A 的最大字母 和 B 的最小字母(其中 A 的最大字母保证严格小于 B 的最大字母),并计算操作数,最后取最小值即可。
代码上,我们需要先统计 A 和 B 的字符出现次数信息,不妨分别记为 counter_A 和 counter_B。接下来,我们就可以执行核心的枚举逻辑了。
核心代码:
1
# 枚举 A 的最大字母
2
for i in range(1, 26):
3
t = 0
4
# A 中大于等于 i 的所有字符都需要进行一次操作
5
for j in range(i, 26):
6
t += counter_A[j]
7
# B 中小于 i 的所有字符都需要进行一次操作
8
for j in range(i):
9
t += counter_B[j]
10
# 枚举的所有情况中取最小的
11
ans = min(ans, t)
Copied!
而对于第三个条件,则比较简单,我们只需要将 A 和 B 改为同一个字母,并计算出操作数,取最小值即可。我们可能修改成的字母一共只有 26 种可能,因此直接枚举即可。
核心代码:
1
for i in range(26):
2
ans = min(ans, len(A) + len(B) - counter_A[i] - counter_B[i])
Copied!

关键点

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

代码

  • 语言支持:Python3
Python3 Code:
1
class Solution:
2
def minCharacters(self, A: str, B: str) -> int:
3
counter_A = [0] * 26
4
counter_B = [0] * 26
5
for a in A:
6
counter_A[ord(a) - ord('a')] += 1
7
for b in B:
8
counter_B[ord(b) - ord('a')] += 1
9
ans = len(A) + len(B)
10
for i in range(26):
11
ans = min(ans, len(A) + len(B) - counter_A[i] - counter_B[i])
12
for i in range(1, 26):
13
t = 0
14
for j in range(i, 26):
15
t += counter_A[j]
16
for j in range(i):
17
t += counter_B[j]
18
ans = min(ans, t)
19
for i in range(1, 26):
20
t = 0
21
for j in range(i, 26):
22
t += counter_B[j]
23
for j in range(i):
24
t += counter_A[j]
25
ans = min(ans, t)
26
return ans
Copied!
我们也可以将操作封装成函数方便理解。其中:
  • greater_cost(a, b) 表示 a 中严格大于 b 的最小操作数。
  • equal_cost(a, b) 表示将 a 和 b 转化为同一字符的最小操作数。
Python3 Code:
1
class Solution:
2
def minCharacters(self, A: str, B: str) -> int:
3
ca = collections.Counter(A)
4
cb = collections.Counter(B)
5
# ca 中严格大于 cb 的最小操作数
6
def greater_cost(ca, cb):
7
ans = float("inf")
8
# 枚举 ca 中的最小值
9
for i in range(1, 26):
10
count = 0
11
# 将 ca 中小于最小值的都进行一次操作
12
for j in range(i):
13
count += ca[chr(97 + j)]
14
# 将 cb 中大于等于最小值的都进行一次操作(注意这里的等号)
15
for j in range(i, 26):
16
count += cb[chr(97 + j)]
17
ans = min(ans, count)
18
return ans
19
20
def equal_cost(ca, cb):
21
ans = float("inf")
22
for i in range(26):
23
ans = min(ans, len(A) + len(B) - ca[chr(97 + i)] - cb[chr(97 + i)])
24
return ans
25
26
return min(greater_cost(ca, cb), greater_cost(cb, ca), equal_cost(ca, cb))
Copied!
复杂度分析
令 m, n 分别为数组 A 和数组 B 的长度。
  • 时间复杂度:$O(m + n)$
  • 空间复杂度:$O(26)$
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。