题解 | 牛牛喜欢字符串

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



int main() {
    // 加速cin/cout的输入输出速度，避免同步带来的延迟
    cin.tie(0)->sync_with_stdio(0);
    ll n,k;
    cin>>n>>k;  // 读取字符串长度n和分组长度k
    vector<char>s(n+1);
    for(ll i=1;i<=n;i++){
        cin>>s[i];  // 读取字符串，下标从1开始存储
    }
    ll res=0;  // 存储最少操作次数的结果
    // 遍历每组的第i个位置（共k个位置，对应所有分组的同位置字符）
    for(ll i=1;i<=k;i++){
        // 哈希表t：统计当前位置i对应的所有字符的出现次数
        // m：记录当前位置中出现次数最多的字符的出现次数
        unordered_map<char,ll>t;
        ll m=0;
        // 遍历所有分组中第i个位置的字符（j从i开始，每次步长为k，覆盖所有组的第i位）
        for(ll j=i;j<=n;j+=k){
            if(t.find(s[j])==t.end()){
                t[s[j]]=1;  // 字符首次出现，初始化次数为1
                m=max(t[s[j]],m);  // 更新最大出现次数
            }
            else{
                t[s[j]]++;  // 字符已存在，次数+1
                m=max(t[s[j]],m);  // 更新最大出现次数
            }
        }
        // 该位置的修改次数 = 总组数（n/k） - 出现次数最多的字符的次数，累加到结果
        res+=n/k-m;
    }
    cout<<res;  // 输出最少操作次数
    return 0;   
}