核心算法：贪心

竖向切片

我们可以将这 个长度为 的子串想象成一个 的字符矩阵：

  • 第 1 行：
  • 第 2 行：
  • ...
  • 第 行：

目标转化： 要是所有行（子串）完全相同，意味着在这个矩阵中，每一列的所有字符必须相同。 由于不同列之间的字符选择是相互独立的，我们可以将大问题分解为 个独立的子问题：尽可能少地修改每一列的字符，使其变为单一字符。

局部最优

对于矩阵的第 列（其中 ），该列包含的字符是原字符串中索引为 的所有字符。 假设这一列包含 个字符。为了让这一列变为全等的字符 ，我们需要修改的次数为： 其中 是字符 在第 列中出现的次数。

为了使 最小化，显然我们需要选择该列中出现频率最高的字符作为目标字符（即众数）。 保留出现次数最多的字符，修改其余字符，这就是局部最优解。

全局最优解

由于列与列之间互不影响，全局最小修改次数等于所有列的最小修改次数之和。 或者更直观地： 即：总长度 - 所有位置上保留下来的字符总数。

复杂度分析

时间复杂度

  • 外层循环：遍历 到 ，共 次。
  • 内层逻辑：对于每个 ，我们以步长 遍历整个字符串。
  • 总遍历次数相当于访问了字符串的每一个字符恰好一次。
  • 寻找大小为 26 的数组的最大值是常数操作 （更准确地说是 ）。
  • 总时间复杂度：。

空间复杂度

  • 我们不需要存储整个二维矩阵，也不需要存储所有列的统计结果。
  • 只需要一个大小为 26 的临时数组 freq 来存储当前列的统计信息。
  • 总空间复杂度：（假设字符集大小固定为 26）。
    • 这种空间优化方案避免了当 很大时可能出现的内存压力。

代码实现

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

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

    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    int ans = n;

    for (int j = 0; j < k; j++) {
        array<int, 26> cnt{};
        int mx = 0;
        for (int i = j; i < n; i += k) {
            int v = s[i] - 'a';
            cnt[v]++;
            mx = max(mx, cnt[v]);
        }
        ans -= mx;
    }

    cout << ans << endl;
}