1737. 满足三条件之一需改变的最少字符数#

1
给你两个字符串 a 和 b ，二者均由小写字母组成。一步操作中，
2

3
你可以将 a 或 b 中的 任一字符 改变为 任一小写字母 。
4

5
操作的最终目标是满足下列三个条件 之一 ：
6

7
a 中的 每个字母 在字母表中 严格小于 b 中的 每个字母 。
8
b 中的 每个字母 在字母表中 严格小于 a 中的 每个字母 。
9
a 和 b 都 由 同一个 字母组成。
10
返回达成目标所需的 最少 操作数。
11

12

13

14
示例 1：
15

16
输入：a = "aba", b = "caa"
17
输出：2
18
解释：满足每个条件的最佳方案分别是：
19
1) 将 b 变为 "ccc"，2 次操作，满足 a 中的每个字母都小于 b 中的每个字母；
20
2) 将 a 变为 "bbb" 并将 b 变为 "aaa"，3 次操作，满足 b 中的每个字母都小于 a 中的每个字母；
21
3) 将 a 变为 "aaa" 并将 b 变为 "aaa"，2 次操作，满足 a 和 b 由同一个字母组成。
22
最佳的方案只需要 2 次操作（满足条件 1 或者条件 3）。
23
示例 2：
24

25
输入：a = "dabadd", b = "cda"
26
输出：3
27
解释：满足条件 1 的最佳方案是将 b 变为 "eee" 。
28

29

30
提示：
31

32
1 <= a.length, b.length <= 105
33
a 和 b 只由小写字母组成

1
class Solution {
2
public:
3
    int minCharacters(string a, string b) {
4
        int n = a.size(), m = b.size();
5
        int l[26] = {0};
6
        int r[26] = {0};
7
        for(auto x : a)
8
        {
9
            l[x - 'a']++;
10
        }
11
        for(auto x : b)
12
        {
13
            r[x - 'a']++;
14
        }
15
        int ls = 0;
16
        int rs = 0;
17
        int ans = n + m;
18
        for (int i = 0; i < 25; ++i)
19
        {
20
            ls += l[i];
21
            rs += r[i];
22
            ans = min(ans, min(min(n + m - l[i] - r[i], n - ls + rs), m - rs + ls));
23
        }
24
        ans = min(ans, n + m - l[25] - r[25]);
25
        return ans;
26
    }
27
};