原理

问题目标：统计单词中各字母出现次数的最大值与最小值的差，判断该差是否为质数。

• ​核心逻辑：
  1. ​统计频率：使用哈希表记录每个字母的出现次数。
  2. ​极值计算：遍历哈希表找到最大和最小出现次数。
  3. ​质数判断：若差值大于 1 且是质数，输出 Lucky Word 和差值；否则输出 No Answer 和 0。

步骤

1. ​输入处理：读取字符串并统计每个字符的出现次数（哈希表）。
2. ​极值查找：
   • 初始化 maxn 为最小值（0），minn 为最大值（100）。
   • 遍历哈希表，更新 maxn 和 minn。
3. ​差值计算：计算 maxn - minn。
4. ​质数判断：
   • 若差值为质数且大于 1，输出 Lucky Word 和差值。
   • 否则输出 No Answer 和 0。

图示法表示步骤（示例输入 "error"）

1. ​统计频率：
   • e:1, r:2, o:1
2. ​极值查找：
   • maxn = 2, minn = 1
3. ​差值计算：2 - 1 = 1
4. ​质数判断：1 不是质数 → 输出 No Answer 0。

代码关键行注释

unordered_map<char, int> umap;  
for (int i = 0; i < s.size(); i++) umap[s[i]]++;  
// 统计每个字符的出现次数，时间复杂度 O(n)  

int maxn = 0, minn = 100;  
for (auto& pair : vec) {  
    if (pair.second > maxn) maxn = pair.second;  // 更新最大值  
    if (pair.second < minn) minn = pair.second;  // 更新最小值  
}  
// 遍历哈希表找极值，时间复杂度 O(m)（m 为不同字符数）  

bool is_prime(int n) { ... }  
// 质数判断函数，时间复杂度 O(√n)  

完整代码程序

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

bool is_prime(int n){
    if(n<=1) return false;
    if(n==2) return true;
    if(n%2==0) return false;
    for(int i=3;i*i<=n;i+=2){
        if(n%i==0) return false;
    }
    return true;
}

int main(){
    string s;
    cin>>s;
    unordered_map<char,int> umap;
    for(int i=0;i<s.size();i++){
        umap[s[i]]++;
    }
    vector<pair<char,int>> vec(umap.begin(),umap.end());
    int maxn=0;
    for(int i=0;i<vec.size();i++){
        if(vec[i].second>maxn) maxn=vec[i].second;
    }
    int minn=100;
    for(int i=0;i<vec.size();i++){
        if(vec[i].second<minn) minn=vec[i].second;
    }

    int ans=maxn-minn;
    if(is_prime(ans)){
        cout<<"Lucky Word"<<endl;
        cout<<ans<<endl;
    }else{
        cout<<"No Answer"<<endl;
        cout<<0<<endl;
    }


    return 0;
}

时间复杂度

• ​时间复杂度：
  • ​统计频率：O(n)，遍历字符串一次。
  • ​极值查找：O(m)，m 为不同字符数（最多 26）。
  • ​质数判断：O(√ans)，ans 为差值。
  • ​总复杂度：O(n + √ans)。
• ​空间复杂度：O(m)，存储哈希表和极值结果。

总结

1. ​代码特点：
   • ​简洁性：直接利用哈希表统计频率，逻辑清晰。
   • ​效率：质数判断优化到 O(√ans)，适用于常规输入。
2. ​潜在问题：
   • ​极值初始化风险：minn 初始值设为 100，若所有字符出现次数均 ≥100（如超长字符串），会得到错误结果。
   • ​字符范围限制：仅支持 ASCII 字符，但对题目要求足够。
3. ​改进建议：
   • 将 minn 初始化为 INT_MAX 或第一个字符的出现次数，避免极端情况错误。
   • 若题目允许，可用固定大小数组（长度 26）代替哈希表，优化空间。