题意分析

异位词（anagram）是指一个单词的字母重新排列后能形成另一个单词（例如 "occurs" 和 "succor"）。异位词距离定义为：为了使两个单词的剩余部分成为异位词，需要移除的最小字母数量。具体规则：

• 两个单词的字母频率必须完全一致才能成为异位词（例如 "dear" 和 "dared" 不是异位词，因为 'd' 的频率不同）。
• 距离计算公式：设单词 A 和 B 的长度分别为 $\text{len}_A$ 和 $\text{len}_B$，最大匹配部分的长度是所有字母中最小频率之和（即 $ \text{sum\_min} = \sum_{i=a}^{z} \min(\text{freq}_A(i), \text{freq}_B(i)) $)。则异位词距离 $ d = \text{len}_A + \text{len}_B - 2 \times \text{sum\_min} $。
  • 示例："sleep" (长度5) 和 "leap" (长度4)，最小频率和：l:1, e:1, p:1（sum_min=3），距离=5+4-2×3=3。
  • 极端情况：若单词无共同字母（如 "dog" 和 "cat"），sum_min=0，距离=3+3-0=6。

代码示例

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

using namespace std;

int main() {
    int N;
    cin >> N;
    cin.ignore(); // 忽略换行符，因为后面用 getline
    for (int i = 1; i <= N; i++) {
        string word1, word2;
        getline(cin, word1); // 读一行，可能空
        getline(cin, word2);
        
        int len1 = word1.length();
        int len2 = word2.length();
        
        // 初始化频率数组
        vector<int> freq1(26, 0);
        vector<int> freq2(26, 0);
        
        // 计算 word1 频率
        for (char c : word1) {
            if (c >= 'a' && c <= 'z') {
                freq1[c - 'a']++;
            }
        }
        
        // 同样为 word2
        for (char c : word2) {
            if (c >= 'a' && c <= 'z') {
                freq2[c - 'a']++;
            }
        }
        
        // 计算 sum of min frequencies
        int sum_min = 0;
        for (int j = 0; j < 26; j++) {
            sum_min += min(freq1[j], freq2[j]);
        }
        
        // 计算距离
        int distance = len1 + len2 - 2 * sum_min;
        
        // 输出
        cout << "Case #" << i << ": " << distance << endl;
    }
    
    return 0;
}

解题思路

1. 核心逻辑：
   • 异位词要求字母频率一致。因此，计算每个单词的字母频率（26 个小写字母）。
   • 最大匹配长度 $\text{sum\_min}$ 是所有字母在两个单词中最小频率之和（例如，字母 'e' 在 A 中出现 2 次，在 B 中出现 1 次，则贡献 min(2,1)=1）。
   • 距离 $ d = \text{len}_A + \text{len}_B - 2 \times \text{sum\_min} $。这是因为：

• 移除的字母数 = (单词 A 中未匹配的字母) + (单词 B 中未匹配的字母)。
• 未匹配部分长度 = $\text{len}_A - \text{sum\_min}$ + $\text{len}_B - \text{sum\_min}$。
• 简化后得上述公式。

2. 算法步骤：

   • 读入数据：读整数 $N$，循环处理每个案例。每个案例读两个字符串（可能为空）。
   • 计算频率：为每个单词创建大小为 26 的频率数组（索引 0-25 对应 a-z）。遍历字符串，统计每个字母出现次数。
   • 计算 sum_min：遍历 26 个字母，累加 $\min(\text{freq}_A[i], \text{freq}_B[i])$。
   • 计算距离：$ d = \text{len}_A + \text{len}_B - 2 \times \text{sum\_min} $。
   • 输出结果：格式化输出 "Case #i: d"。

3. 边界处理：

   • 空单词：长度 0，频率全 0，sum_min=0，距离 = 0 + len - 0 = len（移除所有字母）。
   • 字母均为小写，无需大小写转换。
   • 性能：$N$ 最大 60,000，单词最长 45 字母（如 "pneumonoultramicroscopicsilicovolcanoconiosis"），频率计算 O(n)，整体高效。

4. 示例验证：

   • Case #1: "crocus" 和 "succor"：

• 长度均 6，频率相同（c:2, r:1, o:1, u:1, s:1），sum_min=6。
• d = 6 + 6 - 2×6 = 0。输出 0。