题解 | 牛牛喜欢字符串

我们发现牛牛实际上只关心每组对应位置上的字母是否相同，那么就会很自然且贪心地想到，把出现最多的那个字母不动，修改其他字母。首先统计每组的第i个位置各个字母的数量，存储方式可以用数组或者哈希表来存储。然后枚举0~k-1个位置，每次ans都累加所有字母数(实际上就是n/k，有n个字母，每k个字母一组，一共分成了n/k组)减去出现最多的那个字母的数量。时间复杂度为O(max{n,k*26})，n和k的数据量最大为1E6，那么最坏情况下需要处理2.6E7次O(1)的操作，使用C++不会超时。

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

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int n,k;
  std::cin >> n >> k;

  std::string s;
  std::cin >> s;

  auto cnt = std::vector(k,std::vector<int>(26));

  for(int i = 0; i < n; i++){
    cnt[i%k][s[i]-'a']++;
  }

  int ans = 0;
  for(int i = 0; i < k; i++){
    int max = 0;

    for(int j = 0; j < 26; j++){
      max = std::max(max,cnt[i][j]);
    }
    
    ans += n/k-max;
  }

  std::cout << ans << "\n";
}