蓝桥杯国赛真题解析：字符串重复构造与贪心算法实战

1. 项目概述从一道国赛真题看字符串问题的核心最近在整理历年蓝桥杯的真题翻到了第十一届国赛Java大学B组的这道“重复字符串”。这道题乍一看题目描述很简单但真正动手实现时才发现里面藏着不少关于字符串处理、贪心策略和问题拆解的“坑”。很多同学在练习时要么被它的“简单”外表迷惑要么在实现细节上栽了跟头。今天我就结合自己多次刷题和教学的经验把这道题的来龙去脉、核心思路、代码实现以及那些容易忽略的细节掰开揉碎了讲清楚。无论你是正在备赛蓝桥杯的选手还是想巩固字符串与算法基础的Java开发者相信这篇深度解析都能让你有所收获。这道题本质上是一个“构造”问题。它不要求我们去搜索或匹配一个现成的重复字符串而是给定一个字符串允许我们修改其中的任意字符目标是把它变成一个由某个长度为 k 的子串重复多次构成的字符串。我们需要找到最少的修改次数。这听起来有点像“周期字符串”的判断但加入了“修改”这个操作使得问题从单纯的判断变成了带成本的优化一下子就把难度和趣味性都提上来了。2. 问题核心与思路拆解化繁为简的智慧2.1 问题重述与关键点抓取首先我们得把题目意思理解透。题目给定一个字符串 S长度记为 n和一个整数 k且 k 是 n 的约数。我们可以修改 S 中的任意字符每次修改计为一次操作。目标是使修改后的字符串 S‘ 满足S’ 可以由某个长度为 k 的字符串 T 重复 n/k 次得到。我们需要输出达成这个目标所需的最少操作次数。这里有几个至关重要的约束和隐含条件直接决定了我们的解题方向k 必须是 n 的约数这是问题有解的前提。因为最终字符串是由长度为 k 的模板重复而成总长度 n 必须是 k 的整数倍。题目已保证此条件。我们可以任意修改字符这意味着我们拥有“上帝视角”可以通过修改来“统一”字符串的形态而不是被原字符串完全束缚。目标是“最小修改次数”这是一个优化目标。我们不需要输出最终字符串是什么只需要输出最小代价。这提示我们可能不需要真正构造出 T而是可以通过统计和比较来计算出代价。2.2 核心思路分组统计与贪心策略面对这个问题最直接的暴力想法是枚举所有可能的长度为 k 的模板 T共有 26^k 种可能对于 k 稍大就不可行然后计算将 S 修改为对应重复字符串的代价取最小值。这显然是不现实的。我们需要一个更聪明的办法。仔细思考“重复字符串”的结构假设最终答案是模板 T t0t1...t(k-1)那么最终字符串就是 T 重复 m n/k 次。这意味着在最终字符串中所有下标对 k 取模相同的位置字符都必须是一样的。例如设 k3, n9。那么最终字符串中下标为 0, 3, 6 的位置字符必须相同都是 t0下标为 1, 4, 7 的位置字符必须相同都是 t1下标为 2, 5, 8 的位置字符必须相同都是 t2。这个观察是突破的关键它将一个全局的“重复”问题分解成了 k 个独立的“分组一致化”问题。我们不需要关心整个模板 T 是什么只需要分别确定这 k 个组第0组第1组...第k-1组各自应该统一成什么字符使得总修改代价最小。对于第 i 组包含所有下标 mod k i 的字符它包含 m 个字符。我们要把这 m 个字符都变成同一个字母代价就是 m 减去这个字母在当前组中出现的次数因为出现过的字符不需要修改。那么对于第 i 组最优策略显然是将该组所有字符修改为当前组内出现次数最多的那个字符。这样需要修改的次数就是 m - maxCount_i其中 maxCount_i 是第 i 组中出现频率最高的字符的出现次数。因此整体最小修改次数的公式就出来了总最小修改次数 Σ (i从0到k-1) [ m - maxCount_i ]其中m n / k。这个思路就是一个典型的贪心策略。它在每一个局部每个分组都做出当前最优的选择改为出现最多的字符并且可以证明这种局部最优的选择组合起来就是全局最优解。因为各个分组之间是独立的一个分组内的决策不会影响其他分组的代价。注意这里有一个非常重要的细节题目中字符串通常只由小写字母构成蓝桥杯真题默认如此除非特别说明。因此我们统计频率时只需要考虑26个小写字母。这决定了我们频率统计数组的大小。3. 算法实现与代码精讲思路清晰之后实现起来就相对直接了。但“魔鬼在细节中”一个高效、清晰的实现能避免很多不必要的错误。3.1 数据结构设计与初始化我们需要为 k 个分组分别统计 26 个字母出现的次数。一个很自然的数据结构是使用一个二维数组count[k][26]。其中count[i][j]表示在第 i 组中字母 (‘a’j) 出现的次数。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int k sc.nextInt(); sc.nextLine(); // 消耗换行符 String s sc.nextLine(); int n s.length(); // 基础校验k必须是n的约数虽然题目可能保证但养成校验习惯是好的 if (n % k ! 0) { System.out.println(-1); // 或者根据题目要求处理 return; } int m n / k; // 每组字符个数 int[][] count new int[k][26]; // ... 后续代码 } }3.2 核心统计过程接下来我们需要遍历原始字符串 S将每个字符归到对应的组并增加相应的计数。这里下标 i 从 0 到 n-1它所属的组号是i % k字符在字母表中的索引是s.charAt(i) - a。// 统计每个分组中各个字母的出现次数 for (int i 0; i n; i) { char c s.charAt(i); int groupIndex i % k; int charIndex c - a; count[groupIndex][charIndex]; }3.3 计算最小操作数统计完成后遍历每个分组找出该分组中出现次数最多的字母的出现次数maxCount那么修改这个分组需要的操作数就是m - maxCount。将所有分组的操作数累加即可。int totalOperations 0; for (int i 0; i k; i) { int maxCountInGroup 0; for (int j 0; j 26; j) { if (count[i][j] maxCountInGroup) { maxCountInGroup count[i][j]; } } totalOperations (m - maxCountInGroup); } System.out.println(totalOperations);3.4 完整代码与复杂度分析将上述片段组合起来就是完整的解决方案import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int k sc.nextInt(); sc.nextLine(); // 消耗掉数字后的换行符 String s sc.nextLine(); int n s.length(); // 校验k是否为n的约数 if (n % k ! 0) { // 根据题目实际要求处理这里假设输入合法但防御性编程是好的 // System.out.println(-1); // return; } int m n / k; // 每个分组应有的字符数 int[][] freq new int[k][26]; // freq[group][letter] // 1. 统计频率 for (int i 0; i n; i) { char c s.charAt(i); int group i % k; int letterIdx c - a; freq[group][letterIdx]; } // 2. 计算总操作数 int ans 0; for (int group 0; group k; group) { int maxFreqInGroup 0; for (int letter 0; letter 26; letter) { maxFreqInGroup Math.max(maxFreqInGroup, freq[group][letter]); } ans (m - maxFreqInGroup); } System.out.println(ans); sc.close(); } }时间复杂度分析我们遍历了一次字符串进行统计复杂度为 O(n)。然后遍历了 k 个分组每个分组检查26个字母复杂度为 O(26*k) O(k)。由于 k n且通常 k 远小于 n所以总时间复杂度为 O(n)对于 n 高达 10^5 的数据范围也完全可行。空间复杂度分析我们使用了一个 k x 26 的二维数组。由于 k n且 26 是常数所以空间复杂度为 O(k)在合理范围内。4. 关键细节与避坑指南这道题思路清晰代码简短但我在自己实现和看学生代码时还是发现了几个高频的“翻车点”。4.1 输入处理的陷阱这是一个非常经典的坑。题目输入通常是先读整数 k再读字符串 s。如果使用Scanner.nextInt()读取 k它会读取数字但不会消耗数字后面的换行符\n。紧接着使用Scanner.nextLine()读取字符串时会立刻读到那个剩下的换行符得到一个空字符串。错误示范int k sc.nextInt(); String s sc.nextLine(); // s 在这里很可能是一个空字符串正确做法在nextInt()后额外调用一次nextLine()来“吞掉”那个换行符。int k sc.nextInt(); sc.nextLine(); // 消耗换行符 String s sc.nextLine();或者更直接地全部用nextLine()读取然后对第一行进行解析int k Integer.parseInt(sc.nextLine()); String s sc.nextLine();4.2 分组逻辑与下标映射的确认“所有下标对 k 取模相同的位置属于同一组”这个逻辑务必在脑子里和代码里反复确认。循环变量i是字符串的下标0-based组号是i % k。我见过有同学写成了i / k这是完全不同的分组方式它是按连续块分组会导致结果错误。你可以通过一个简单例子验证s “abcdef”, k2。正确分组i % 2组0: a(0), c(2), e(4)组1: b(1), d(3), f(5)。错误分组i / 2组0: a(0), b(1)组2: c(2), d(3)组3: e(4), f(5)。这显然不符合“重复周期为2”的定义。4.3 字符到索引的转换s.charAt(i) - ‘a’这个操作能正确工作前提是字符串确实只包含小写字母。在竞赛中这通常是默认的。但如果题目没有明确说明或者未来遇到变种题这里就需要小心。如果包含大写字母或其他字符直接减 ‘a’ 会产生负数或超出数组范围的索引导致ArrayIndexOutOfBoundsException。防御性做法如果输入范围不确定可以在统计前进行判断或者使用容量更大的数组如128对应ASCII码。char c s.charAt(i); if (c a c z) { int idx c - a; freq[group][idx]; } // 或者根据题目要求处理非小写字母的情况4.4 当心整数除法与求余运算虽然题目保证了 k 是 n 的约数n % k 0成立m n / k也是整数。但在一些变种或自己思考时要明确这一点。如果 k 不是 n 的约数那么问题可能无解无法构成完整的重复字符串或者需要定义不同的处理规则如允许最后一段不完整。本题中这是一个重要的简化条件。5. 思路延伸与变种思考掌握了一道题的解法最好能举一反三。围绕“重复字符串”和“分组贪心”这个核心我们可以思考一些变种问题这对提升算法思维很有帮助。5.1 变种一允许增加或删除字符如果操作不仅仅是修改还可以在任意位置增加或删除一个字符每次操作代价为1目标仍然是构成一个周期为 k 的重复字符串求最小总代价。这个问题就变成了一个编辑距离类问题的变种难度会大幅提升可能需要用动态规划来解决。状态设计可能会考虑当前处理到的位置以及当前周期内的偏移状态。5.2 变种二寻找最优的 k原题中 k 是给定的。如果 k 不是给定的我们需要找到那个能使总操作次数最小的 kk 必须是 n 的约数并输出最小的操作次数。那么我们就需要枚举 n 的所有正约数 k对每个 k 都运行一遍上述算法然后取总操作次数的最小值。枚举约数的复杂度是 O(√n)对每个约数 k 需要 O(n) 的时间计算总复杂度约为 O(n * d(n))其中 d(n) 是 n 的约数个数。对于 n 较大时需要评估是否可行。5.3 变种三模板T必须来自原字符串如果要求最终重复的模板 T 必须是原字符串 S 中某个长度为 k 的连续子串不能随意构造那么问题就变成了在 S 中寻找一个长度为 k 的子串使得以它为模板重复构造字符串时修改原字符串的代价最小。这需要枚举所有起始位置 i (0 i n-k) 的子串作为候选 T然后计算代价。计算代价时同样可以利用分组思想但此时每个位置的目标字符是固定的由 T 决定代价就是统计该位置上与目标字符不同的字符数。总复杂度为 O(k * (n-k))如果 k 较小则可行。5.4 与“周期字符串”判定的关联经典的周期字符串判定问题如 KMP 算法求 next 数组判断最小周期是判断一个字符串是否本身具有周期性。而本题是“强制”赋予它一个周期性并计算代价。我们可以思考如果最小修改次数为 0那么原字符串 S 本身就是一个周期为 k 的字符串。因此我们的算法也可以作为一种“近似周期”的度量工具。6. 调试与测试用例设计再好的思路没有经过充分测试的代码也是不可靠的。分享几个我用来测试这道题的不同类型的用例覆盖了各种边界和特殊情况。基础用例输入k2, s“aabb”输出0。解释本身就可以看成 “ab” 重复两次。输入k3, s“abcabcabz”输出1。解释n9, m3。分组(a,a,a)(b,b,b)(c,c,z)。第三组最多的是 ‘c’出现2次需要修改1次把z改成c。全相同字符输入k5, s“aaaaaaaaaa”(n10) 输出0。任何分组内所有字符都相同无需修改。全不同字符且无法利用重复输入k1, s“abcdef”输出5。解释k1意味着最终所有字符必须相同。选择出现次数最多的字符任意一个出现1次需要修改 n - 1 5次。输入kn, s“abcdef”(n6) 输出5。解释kn意味着模板长度就是整个字符串不能重复。实际上等价于 k1 的情况所有字符必须相同。随机大字符串测试可以自己写个程序生成随机字符串和 k用暴力枚举小 k 的情况比如 k5来验证算法的正确性。这是验证贪心策略是否正确的有效方法。实操心得在竞赛中写完代码后不要只用题目给的样例。一定要自己设计几个像上面这样的“极端用例”和“简单可手算的用例”快速验证。这往往能帮你提前发现数组越界、除零错误、逻辑疏忽等问题。7. 算法背后的思维模式总结回顾这道“重复字符串”问题它的解决过程体现了几种非常重要的算法和编程思维模式问题转化与分解这是最核心的一步。将全局的“构造重复字符串”问题通过发现“同余下标字符必须相同”这一性质分解为 k 个独立的、更简单的“使一组字符相同”的子问题。这种“化整为零”的思想在解决复杂问题时非常常用。贪心选择策略在每个子问题中我们采用了直观且正确的贪心策略将组内所有字符改为出现频率最高的字符。对于这个独立子问题这明显是最优的。由于子问题间相互独立局部最优解就构成了全局最优解。计数与统计的应用字符串问题中当字符集有限如26个小写字母时使用数组进行频率统计是最高效的方法之一。它避免了使用Map带来的额外开销将比较操作转化为数组查找。模运算与分组处理利用取模运算%进行循环分组是处理周期性、间隔性问题的标准技巧。在密码学、信号处理、并发编程等许多领域都有类似应用。这道题代码量不大但完美地串联了这些基础且重要的概念。把它吃透意义远不止于解决一道竞赛题。下次当你遇到需要周期性处理、分组优化或者需要统一某些元素的问题时不妨想想是否也能用类似的“分组统计贪心”的思路来破解。编程和算法的提升正是在这一次次对经典问题的深度思考和举一反三中积累起来的。