Leetcode-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 只由小写字母组成

题目链接：地址

 

分析

1. 首先用两个数组分别把两个字符串Hash化，<key:小写字母, value:字符串中该字母的个数>，

所以每个数组大小只需26

(我用27是因为当时不想多声明两个变量)

2. 遍历hash map，找最小操作数

如果此时要满足条件一，

即A字符串中每个字母都小于B字符串中的每个字母，

则需要将A字符串中蓝色部分对应的字母替换为绿色对应的字母(任意替换)，将B字符串中蓝色部分对应的字母替换为绿色对应的字母(任意替换)。

如果此时要满足条件二，

即B字符串中每个字母都小于A字符串中的每个字母，

则需要将A字符串中绿色部分对应的字母替换为蓝色对应的字母(任意替换)，将B字符串中绿色部分对应的字母替换为蓝色对应的字母(任意替换)。

最终效果如下图所示：

A的替换次数+B的替换次数 = 达成目标所需的操作数。

所以 最小的操作数= min("满足条件一所需的操作数", "满足条件二所需的操作数");

 

若要要满足条件三：

例如：将A、B都置换为“由小写字母c构成的字符串”

即将除了‘c’以外的所有字母都换成‘c’所需要的代价。

例如："abcde"和"pppc" 满足条件三需要做4+3次置换。

 

总体来说，从小写字母a遍历到小写字母y(不是z，这一点可以画图验证一下)，就是求满足任一条件下的最小值。

代码

class Solution {
    public int minCharacters(String a, String b) {
        int[] arr = new int[27];
        int[] brr = new int[27];
        int len_a = a.length(), len_b = b.length(), result = Integer.MAX_VALUE;
        for(int i = 0; i < a.length(); i++){
            arr[a.charAt(i) - 'a']++;
        }
        for(int i = 0; i < b.length(); i++){
            brr[b.charAt(i) - 'a']++;
        }

        for(int i = 0; i < 25; i++) {
            arr[26] += arr[i];
            brr[26] += brr[i];
            result = Math.min(Math.min(result, len_a + len_b - arr[i] -brr[i]), Math.min(brr[26] + len_a - arr[26], arr[26] + len_b - brr[26]));
        }
        return Math.min(result, len_a + len_b - arr[25] -brr[25]);
    }
}