题解 | #小牛的作业#

题目链接

小牛的作业

题目描述

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

删除 $s$ 中的任意一个字符。
将 $s$ 中的任意一个字符修改为任意一个小写字母。

要求计算，将字符串 $s$ 转变为一个新字符串 $s'$ 所需的最小操作次数，使得 $s'$ 中所有字符的出现次数与 $t$ 中完全相同。若不可能，则输出 -1。

解题思路

这道题的核心是匹配字符的频率，而不是字符串本身。因此，字符的顺序是无关紧要的，我们可以通过频率统计来解决问题。

判断无解情况: 我们的目标是得到一个新字符串 $s'$ ，它的字符频率与 $t$ 相同。这意味着 $s'$ 的总长度必须等于 $t$ 的总长度，即 $|s'| = |t|$ 。我们能对 $s$ 进行的操作只有“删除”（使长度减一）和“修改”（长度不变），我们无法增加 $s$ 的长度。因此，如果初始字符串 $s$ 的长度就小于 $t$ 的长度（ $|s| < |t|$ ），我们永远无法得到长度为 $|t|$ 的 $s'$ 。这种情况下，任务不可能完成，应输出 -1。
计算最小操作次数: 在有解的情况下（ $|s| \ge |t|$ ），问题就转化为：如何用最少的操作，将 $s$ 的字符频率分布调整成和 $t$ 一样。我们可以使用两个大小为 26 的数组 freq_s 和 freq_t 来分别统计两个字符串中每个字母的出现次数。

解题的关键在于找出 $s$ 中有多少字符可以“直接复用”来满足 $t$ 的需求。
- 对于任意一个字符 $c$ （'a' 到 'z'）， $s$ 中有 freq_s[c] 个，而 $t$ 需要 freq_t[c] 个。
- 那么，我们最多可以保留 $\min(freq_s[c], freq_t[c])$ 个字符 $c$ ，这些字符无需任何操作。
将所有 26 个字母可以保留的数量相加，就得到了两个字符串频率分布的“交集”，也就是不需要操作的字符总数

字符串 $s$ 的总长度是 $|s|$ 。其中， $common\_chars$ 个字符被我们保留了。那么，剩下的 $|s| - common\_chars$ 个字符就是 $s$ 中“多余的”、“无法直接复用”的字符。

对于这部分多余的字符，我们必须对它们每一个都进行一次操作（要么是删除，要么是修改），才能最终满足 $t$ 的频率要求。因此，最小操作次数就等于这部分多余字符的数量。

最终公式: $\text{最小操作次数} = |s| - common\_chars$

代码

cpp
java
python

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    if (s.length() < t.length()) {
        cout << -1 << endl;
        return 0;
    }

    vector<int> freq_s(26, 0);
    for (char c : s) {
        freq_s[c - 'a']++;
    }

    vector<int> freq_t(26, 0);
    for (char c : t) {
        freq_t[c - 'a']++;
    }

    int common_chars = 0;
    for (int i = 0; i < 26; ++i) {
        common_chars += min(freq_s[i], freq_t[i]);
    }

    cout << s.length() - common_chars << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String t = sc.nextLine();

        if (s.length() < t.length()) {
            System.out.println(-1);
            return;
        }

        int[] freq_s = new int[26];
        for (char c : s.toCharArray()) {
            freq_s[c - 'a']++;
        }

        int[] freq_t = new int[26];
        for (char c : t.toCharArray()) {
            freq_t[c - 'a']++;
        }

        int common_chars = 0;
        for (int i = 0; i < 26; i++) {
            common_chars += Math.min(freq_s[i], freq_t[i]);
        }

        System.out.println(s.length() - common_chars);
    }
}

import sys

def solve():
    s = sys.stdin.readline().strip()
    t = sys.stdin.readline().strip()

    if len(s) < len(t):
        print(-1)
        return

    freq_s = [0] * 26
    for char in s:
        freq_s[ord(char) - ord('a')] += 1
    
    freq_t = [0] * 26
    for char in t:
        freq_t[ord(char) - ord('a')] += 1

    common_chars = 0
    for i in range(26):
        common_chars += min(freq_s[i], freq_t[i])
        
    print(len(s) - common_chars)

solve()

算法及复杂度

算法: 贪心、频率统计
时间复杂度: 我们需要遍历字符串 $s$ 和 $t$ 来统计频率，时间复杂度为 $\mathcal{O}(|s| + |t|)$ 。之后计算公共字符数需要遍历一次大小为 26 的频率数组，是常数时间。所以总的时间复杂度为 $\mathcal{O}(|s| + |t|)$ 。
空间复杂度: 我们使用了两个大小为 26 的数组来存储频率，因此空间复杂度为 $\mathcal{O}(1)$ （因为字母表大小是常数）。