解题思路

这道题的目标是通过修改字符串中的字符，使其具有最小的严格循环节长度。在不超过 $k$ 次操作的限制下，需要计算可能的最小循环节长度。解题的关键在于如何有效地计算在不同循环节长度下所需的最小修改次数。

核心思路

1. 循环节长度遍历：

   • 对于字符串 $s$ 的每个可能的循环节长度 $l$，从 $1$ 到 $|s|$ 进行遍历。
   • 检查 $l$ 是否能整除 $|s|$，即 $|s| \% l == 0$，只有这样的 $l$ 才有可能成为循环节长度。

2. 计算最小修改次数：

   • 对于每个可能的循环节长度 $l$，计算将字符串变成以 $l$ 为循环节长度所需的最小修改次数。
   • 具体方法是对于每个长度为 $l$ 的位置，统计所有该位置的字符出现频率，找出出现最多的字符，并计算需要修改的次数，使得该位置上的所有字符都变成最多出现的字符。
   • 总修改次数为每个位置所需的修改次数之和。

3. 判断是否满足条件：

   • 对于每个可能的循环节长度 $l$，如果所需的最小修改次数不超过 $k$，则该长度 $l$ 即为可能的最小严格循环节长度，返回该长度。

4. 返回结果：

   • 如果遍历完所有可能的循环节长度，未找到满足条件的长度，则返回字符串的总长度 $|s|$ 作为严格循环节长度。

详细讲解

1. 函数 getmin：

   • 输入：字符串 s 和循环节长度 l。
   • 输出：将字符串变为以 l 为循环节长度所需的最小修改次数。
   • 步骤：
     • 初始化总修改次数 c 为 0。
     • 对于每个位置 $i$ (从 0 到 $l-1$)，统计以 $l$ 为步长的所有字符出现频率。
     • 找出出现最多的字符，并计算将其他字符修改为该字符所需的次数。
     • 累加所有位置的修改次数，即为总修改次数 c。

2. 函数 getans：

   • 输入：整数 k 和字符串 s。
   • 输出：在不超过 $k$ 次修改情况下，使字符串变为最小严格循环节长度的长度。
   • 步骤：
     • 遍历所有可能的循环节长度 l (从 1 到 $|s|$)。
     • 对于每个长度 l，如果 |s| \% l == 0，则调用 getmin(s, l) 计算最小修改次数。
     • 如果最小修改次数不超过 $k$，返回该长度 l。
     • 如果没有找到满足条件的长度，返回字符串的总长度 $|s|$。

代码实现

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

// 获取当前长度 l 下需要的最小修改次数
int getmin(string s, int l) {
    int lens = s.length();
    int c = 0;

    for (int i = 0; i < l; ++i) {
        vector<int> f(26, 0); 
        for (int j = i; j < lens; j += l) {
            f[s[j] - 'a']++;
        }

        int maxx = *max_element(f.begin(), f.end());//max_element(u, v)  求(u, v)之间最大值
        int all = (lens - i + l - 1) / l;

        c += all - maxx;
    }

    return c;
}

// 获取最小的严格循环节长度
int getans(int k, string s) {
    int lens = s.length();

    for (int l = 1; l <= lens; ++l) {
        if (lens % l == 0) {
            if (getmin(s, l) <= k) {
                return l;
            }
        }
    }
    return lens;
}

int main() {
    int k;
    string s;
    cin >> k >> s;
    cout << getans(k, s) << endl;
    return 0;
}

复杂度分析

• 时间复杂度：
  • 函数 getmin 的时间复杂度为 $O(n \cdot \frac{n}{l})$，其中 $n$ 为字符串的长度，$l$ 为循环节长度。
  • 函数 getans 遍历所有可能的循环节长度，时间复杂度为 $O(n^2)$。
• 空间复杂度：
  • 使用了长度为 26 的频率数组 f，空间复杂度为 $O(1)$。

审核大大求过