题解 | #小美的字符串匹配度#

看我的，看我的，时间复杂度是O(n)。详细解释放在代码中，欢迎交流。

#include <iostream>
using namespace std;
#include <array>
#include <unordered_set>
#include <set>

int main() {
    int n;
    string s;
    string t;
    scanf("%d",&n);
    cin>>s;
    cin>>t;

    int res = 0;
    int w = 0; //权重w的范围[0,2]
    array<int,26> f_s={0}; //统计字符出现的频率
    array<int,26> f_t={0};
    set<pair<char,char>> us;
    for(int i=0;i<n;++i){
        if(s[i] == t[i]){
            ++res;
        }
        else{ //仅不匹配的参与统计
            f_s[s[i]-'a']++;
            f_t[t[i]-'a']++;
            us.emplace(s[i],t[i]);
            if(us.find({t[i],s[i]})!=us.end()){//看看前面是否出现了t[i],s[i]如果，出现了刚好和现在的这一对交换，则增加2匹配度
                w=2;
            }
        }
    }
    for(int i=0;i<26;++i){
       if(f_s[i]>0&&f_t[i]>0){ //如果二者同时都存在相同的字符，那说明是可以让两者的匹配度加1的
            w=max(w,1); //取max的原因是，存在可以成对交换的字符
            break;
       }
    }

    res+=w; //加上权重,记为最终答案
    cout << res <<endl;
    return 0;
}