11285770 小牛的作业

题目链接: https://www.nowcoder.com/practice/2003093910a142509157fa2f94088a0d

标签: 字符串, 贪心

---

题意

给两个仅含小写英文字母的字符串 和 。对 可执行两种操作：

1. 删除 中任意一个字符（代价 1）
2. 将 中任意一个字符改为任意字母（代价 1）

目标：将 变为某个字符串 ，使得 与 的字符出现频率完全相同。求最小操作次数，无解输出 -1。

---

分析

无解条件

由于只能删除或修改，不能增加字符，所以最终字符串长度 。而 的长度必须等于 （因为频率分布相同）。

因此，若 ，输出 -1。

最优策略

当 时：

• 必须执行 次删除操作（每次删除代价 1）
• 对剩余的 个字符，希望尽可能多地保留已经"有用"的字符

关键观察：最终 的字符分布与 相同，所以对每个字母 ，最多可以保留 个 不变（ 和 分别是 在 和 中的频率）。

$$

注意到 ，所以这个量总是合法的。

剩余 个位置需要通过修改来补足 中不足的字符，代价为 。

总操作数

$$

为什么不能更优？

• 删除是强制的：最终长度必须为 ，所以必须删除 个字符。
• 修改次数的下界：最终 需要 个字符 ，而 中最多提供 个免费匹配，因此至少需要修改 次。
• 贪心最优：选取所有能匹配的字符即可达到下界。

---

示例

示例 1：s = "abc", t = "cde"

• ，无需删除
• : a=1, b=1, c=1；: c=1, d=1, e=1
• free_matches = min(0,0)+min(0,0)+min(1,1)+min(0,1)+min(0,1) = 1（仅 c 匹配）
• 修改次数 = 3 - 1 = 2
• 答案 = 0 + 2 = 2 ✓

示例 2：s = "abc", t = "cdef"

• ，输出 -1 ✓

---

代码

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s, t;
    cin >> s >> t;

    int n = s.size(), m = t.size();

    if (n < m) {
        cout << -1 << endl;
        return 0;
    }

    int fs[26] = {}, ft[26] = {};
    for (char c : s) fs[c - 'a']++;
    for (char c : t) ft[c - 'a']++;

    int deletions = n - m;
    int free_matches = 0;
    for (int i = 0; i < 26; i++) {
        free_matches += min(fs[i], ft[i]);
    }

    int changes = m - free_matches;
    cout << deletions + changes << endl;

    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine().trim();
        String t = br.readLine().trim();

        int n = s.length(), m = t.length();

        if (n < m) {
            System.out.println(-1);
            return;
        }

        int[] fs = new int[26], ft = new int[26];
        for (char c : s.toCharArray()) fs[c - 'a']++;
        for (char c : t.toCharArray()) ft[c - 'a']++;

        int deletions = n - m;
        int free_matches = 0;
        for (int i = 0; i < 26; i++) {
            free_matches += Math.min(fs[i], ft[i]);
        }

        int changes = m - free_matches;
        System.out.println(deletions + changes);
    }
}

---

复杂度

• 时间：
• 空间：