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

给你两个字符串 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 只由小写字母组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1. 使用前缀和统计字符串中小于某个字母的数字的数目

2. 然后暴力遍历i，将a中的a+’i’左边的字母移到右边，b中a+’i’右边的字母移到左边，记录每个i需要移动的字母的数量

3. 然后暴力遍历i，将b中的a+’i’左边的字母移到右边，a中a+’i’右边的字母移到左边，记录每个i需要移动的字母的数量

4. 还要遍历i，将a中的字母都变成a+’i’记录最小数量

5. 然后三个取最小

class Solution {
    public int minCharacters(String a, String b) {
        int m = a.length();
        int n = b.length();

        // 统计字符数量
        int[] countA = new int[26];
        int[] countB = new int[26];
        for (char c : a.toCharArray()) {
            countA[c - 'a']++;
        }
        for (char c : b.toCharArray()) {
            countB[c - 'a']++;
        }

        // 前缀和preA[i]记录字符串a中<=('a'+i)的字符数
        int[] preA = new int[26];
        for (int i = 0; i < 26; i++) {
            preA[i] = i == 0 ? countA[0] : preA[i - 1] + countA[i];
        }
        // 前缀和preB[i]记录字符串b中<=('a'+i)的字符数
        int[] preB = new int[26];
        for (int i = 0; i < 26; i++) {
            preB[i] = i == 0 ? countB[0] : preB[i - 1] + countB[i];
        }

        // 遍历“分割字符”，收集答案
        int ans = Integer.MAX_VALUE;
        for (char i = 0; i < 26; i++) {
            // 当前分割字符c = 'a'+i
            if (i != 25) {
                // a中全部变成>c, b中全部变成<=c，需要的操作次数
                ans = Math.min(ans, preA[i] + (n - preB[i]));
                // b中全部变成>c, a中全部<=c
                ans = Math.min(ans, (m - preA[i]) + preB[i]);
            }

            // 都转成字符'a'+i，需要的操作次数
            int notEq1 = m - countA[i];
            int notEq2 = n - countB[i];
            ans = Math.min(ans, notEq1 + notEq2);
        }
        return ans;
    }
}

赏

谢谢你请我吃糖果

微信