题目描述
给定两个字符串 a
和 b
,二者均由小写字母组成。一步操作中,你可以将 a
或 b
中的 任一字符 改变为 任一小写字母。
操作的最终目标是满足下列三个条件 之一:
a
中的 每个字母 在字母表中 严格小于b
中的 每个字母。b
中的 每个字母 在字母表中 严格小于a
中的 每个字母。a
和b
都 由 同一个 字母组成。
返回达成目标所需的 最少 操作数。
样例
输入: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)。
输入:a = "dabadd", b = "cda"
输出:3
解释:满足条件 1 的最佳方案是将 b 变为 "eee" 。
限制
1 <= a.length, b.length <= 10^5
a
和b
只由小写字母组成。
算法
(哈希表,前缀和) $O(n + m)$
- 对于条件 1 和 2
- 分别求出
A
和B
两个字符串中,每种字母出现的次数,得到频率数组fa
和fb
。 - 求
fa
和fb
的前缀和。 - 从
a
到y
枚举每个字母 $c$,分别求出将A
所有字母变为小于等于 $c$ 的改变个数和将B
所有字母变为大于 $c$ 的改变个数。 - 同理,求出将
B
所有字母变为小于等于 $c$ 的改变个数和将A
所有字母变为大于 $c$ 的改变个数。
- 分别求出
- 对于条件 3
- 分别求出
A
和B
两个字符串中,每种字母出现的次数,得到频率数组fa
和fb
。 - 从
a
到z
枚举每个字母 $c$,然后求出将A
和B
的所有字母都变为 $c$ 的改变个数。
- 分别求出
时间复杂度
- 遍历两个字符串常数次,故总时间复杂度为 $O(n+m)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
private:
int solve_min(const string &a, const string &b) {
vector<int> fa(26, 0), fb(26, 0);
for (char c : a) fa[c - 'a']++;
for (char c : b) fb[c - 'a']++;
for (int i = 1; i < 26; i++) {
fa[i] += fa[i - 1];
fb[i] += fb[i - 1];
}
int res = INT_MAX;
const int n = a.size(), m = b.size();
for (int i = 0; i < 25; i++) {
res = min(res, n - fa[i] + fb[i]);
res = min(res, m - fb[i] + fa[i]);
}
return res;
}
int solve_equal(const string &a, const string &b) {
vector<int> fa(26, 0), fb(26, 0);
for (char c : a) fa[c - 'a']++;
for (char c : b) fb[c - 'a']++;
int res = INT_MAX;
const int n = a.size(), m = b.size();
for (int i = 0; i < 26; i++)
res = min(res, n - fa[i] + m - fb[i]);
return res;
}
public:
int minCharacters(string a, string b) {
return min(solve_min(a, b), solve_equal(a, b));
}
};