LeetCode 题解工作台
满足三条件之一需改变的最少字符数
给你两个字符串 a 和 b ，二者均由小写字母组成。一步操作中，你可以将 a 或 b 中的 任一字符 改变为 任一小写字母 。 操作的最终目标是满足下列三个条件 之一 ： a 中的 每个字母 在字母表中 严格小于 b 中的 每个字母 。 b 中的 每个字母 在字母表中 严格小于 a 中的 每个字母 …
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 前缀和
答案摘要
我们先统计字符串 和 中每个字母出现的次数，记为 和 。 然后考虑条件 ，即 和 中的每个字母都相同。我们只需要枚举最终的字母 ，然后统计 和 中不是 的字母的个数，即为需要改变的字符个数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 前缀和 题型思路
题目描述
给你两个字符串 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 <= 105a和b只由小写字母组成
解题思路
方法一：计数 + 枚举
我们先统计字符串 和 中每个字母出现的次数，记为 和 。
然后考虑条件 ，即 和 中的每个字母都相同。我们只需要枚举最终的字母 ，然后统计 和 中不是 的字母的个数，即为需要改变的字符个数。
然后考虑条件 和 ，即 中的每个字母都小于 中的每个字母，或者 中的每个字母都小于 中的每个字母。对于条件 ，我们令字符串 所有字符都小于字符 ，字符串 所有字符都不小于 ，枚举 找出最小的答案即可。条件 同理。
最终的答案即为上述三种情况的最小值。
时间复杂度 ，其中 和 分别为字符串 和 的长度，而 为字符集大小。本题中 。
class Solution:
def minCharacters(self, a: str, b: str) -> int:
def f(cnt1, cnt2):
for i in range(1, 26):
t = sum(cnt1[i:]) + sum(cnt2[:i])
nonlocal ans
ans = min(ans, t)
m, n = len(a), len(b)
cnt1 = [0] * 26
cnt2 = [0] * 26
for c in a:
cnt1[ord(c) - ord('a')] += 1
for c in b:
cnt2[ord(c) - ord('a')] += 1
ans = m + n
for c1, c2 in zip(cnt1, cnt2):
ans = min(ans, m + n - c1 - c2)
f(cnt1, cnt2)
f(cnt2, cnt1)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for candidates who can efficiently use hash tables for counting operations.
- question_mark
Evaluate how well the candidate handles the three conditions with a minimal number of iterations.
- question_mark
Check if the candidate can optimize the solution by focusing on constant-time operations for each condition.
常见陷阱
外企场景- error
Failing to use hash tables efficiently can result in unnecessary recalculations.
- error
Incorrectly handling edge cases such as when strings are already equal or when one string is empty.
- error
Not minimizing the operations correctly and selecting suboptimal conditions.
进阶变体
外企场景- arrow_right_alt
Modify the problem by limiting the alphabet to only vowels or consonants.
- arrow_right_alt
Allow a different character set (e.g., uppercase or digits) and test the solution’s scalability.
- arrow_right_alt
Add constraints that require the solution to handle much larger input sizes while maintaining optimal performance.