第 225 场周赛 5662. 满足三条件之一需改变的最少字符数

Desciption

给两个串 a 和 b，都是小写字母。每次操作可以把 一个小写字母 变为 任意一个小写字母 操作的最终目标是满足下列三个条件 之一 ：

  • a 中的 每个字母 在字母表中 严格小于 b 中的 每个字母 。
  • b 中的 每个字母 在字母表中 严格小于 a 中的 每个字母 。
  • a 和 b 都 由 同一个 字母组成 问你，满足三个条件 之一，最少需要操作多少次

Solution

  1. 枚举满足每一个条件的最小操作次数，取最小即可
  2. 满足第三个条件：把 a 和 b 都变成它里面出现次数最多的字母即可
  3. 满足第一个条件： 找出 a 字符串里，字典序最大的字母 mx，然后把 b 串的字母全都变成比 mx 字典序大的字母，或者找出 b 字符串里，字典序最小的字母 mi，然后把 a 串的字母全都变成比 mi 字典序小的字母。这种做法的错误的，因为可以同时修改 a 串和 b 串。考虑枚举字母 X，把 a 串的字母都变成比 X 小的字母，把 b 串的字母都变成大于等于 X 的字母，操作次数的和，取最小，即是满足第一个条件的最少操作次数
  4. 满足第二个条件：跟第一个条件一样，把参数换一下

Code

    public int minCharacters(String a, String b) {
        int ans = getSameChar(a) + getSameChar(b);
        for (int i = 1; i < 26; ++i) {
            ans = Math.min(ans, getSmallChar(a, b, i));
            ans = Math.min(ans, getSmallChar(b, a, i));
        }
        return ans;
    }

    int getSameChar(String a){
        int n = a.length();
        int[] count = new int[26];
        Arrays.fill(count, 0);
        int mx = 0;
        for (int i = 0; i < n; ++i) {
            int x = a.charAt(i) - 'a';
            count[x]++;
            mx = Math.max(mx, count[x]);
        }
        return n - mx;
    }

    int getSmallChar(String a, String b, int v) {
        int n = a.length(), m = b.length();
        int res = 0;
        for (int i = 0; i < n; ++i) {
            int x = a.charAt(i) - 'a';
            if (x >= v) {
                res++;
            }
        }
        for (int i = 0; i < m; ++i) {
            int x = b.charAt(i) - 'a';
            if (x < v) {
                res++;
            }
        }
        return res;
    }