美文网首页
【算法题】1737. 满足三条件之一需改变的最少字符数

【算法题】1737. 满足三条件之一需改变的最少字符数

作者: 程序员小2 | 来源:发表于2023-06-02 08:10 被阅读0次

题目:

给你两个字符串 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 <= 10^5
a 和 b 只由小写字母组成

java代码:

class Solution {
    public int minCharacters(String a, String b) {
        int n = a.length(), m = b.length(), ans = 0x3f3f3f3f;
        int[] c1 = new int[26], c2 = new int[26];
        for (char c : a.toCharArray()) c1[c - 'a']++;
        for (char c : b.toCharArray()) c2[c - 'a']++;
        for (int i = 0; i < 26 && ans != 0; i++) {
            // 3
            int ca = n - c1[i], cb = m - c2[i];
            ans = Math.min(ans, ca + cb);
            if (i == 0) continue;
            int r1 = 0, r2 = 0;
            // 1
            for (int j = i; j < 26; j++) r1 += c1[j];
            for (int j = 0; j < i; j++) r1 += c2[j];
            // 2
            for (int j = i; j < 26; j++) r2 += c2[j];
            for (int j = 0; j < i; j++) r2 += c1[j];
            ans = Math.min(ans, Math.min(r1, r2));
        }
        return ans;
    }
}

相关文章

网友评论

      本文标题:【算法题】1737. 满足三条件之一需改变的最少字符数

      本文链接:https://www.haomeiwen.com/subject/yabpedtx.html