尧图网页设计 解法)
1. 问题背景与核心诉求看到“重复字符串”这个题目很多参加过蓝桥杯或者正在备赛的朋友可能会心一笑或者眉头一皱。这题出自2020年第十一届蓝桥杯国赛算是那届比赛里一道比较有代表性的字符串处理题。它不像动态规划那样需要复杂的状态推导也不像图论那样需要精巧的建模但恰恰是这种“看起来简单”的题目最容易让选手在考场上栽跟头——要么是题意理解偏差要么是边界条件没处理好要么就是算法复杂度没算对导致大规模数据超时。这道题的核心是给定一个字符串要求我们通过修改最少的字符使得这个字符串可以由某个长度为k的子串重复若干次构成。换句话说我们要找到一个“模板”子串把原字符串尽可能多地“对齐”到这个模板上修改那些对不齐的字符。这听起来有点像“周期串”的判断但加上了“允许修改”的操作并且要求修改次数最少一下子就变成了一个最优化问题。我当年第一次做这题时第一反应是暴力枚举所有可能的子串作为模板然后去计算修改成本。这个思路方向是对的但如果没有经过优化对于长度上千的字符串计算量会非常恐怖在竞赛1秒的时间限制内根本跑不完。后来经过反复推敲和测试才找到了那个既直观又高效的解法。今天我就把自己踩过的坑、优化的思路以及完整的Java实现代码毫无保留地分享出来。无论你是正在备赛蓝桥杯还是想巩固字符串和贪心算法这篇文章都能给你带来实实在在的收获。2. 题意深度拆解与数学模型建立拿到题目第一步永远是彻底读懂题意。我们先把抽象的描述转化成具体的数学和逻辑模型。2.1 问题重述假设我们有一个字符串S其长度为n。同时给定一个整数k这个k是我们要寻找的重复单元的长度。题目要求是判断能否将字符串S划分为n / k个连续的长度为k的子串这里隐含n必须能被k整除否则直接无解并且通过修改其中某些位置的字符使得这n / k个子串变得完全相同。我们的目标不是真的去修改字符串而是计算出达成上述目标所需的最少修改次数。如果n不能被k整除则直接输出-1表示无法通过修改达成“重复字符串”。2.2 一个具体例子假设S “ababcabab”,k 3。字符串长度n 99 / 3 3可以分成3个长度为3的子串“aba”,“bca”,“bab”。现在我们需要找到一个长度为3的理想模板比如“aba”。将三个子串与“aba”对比子串1:“aba”- 完全相同修改0次。子串2:“bca”- 位置0的‘b‘需改为‘a‘位置1的‘c‘需改为‘b‘位置2的‘a‘已是‘a‘。共修改2次。子串3:“bab”- 位置0的‘b‘需改为‘a‘位置2的‘b‘需改为‘a‘。共修改2次。总修改次数 0 2 2 4。但“aba”是最优模板吗不一定。我们需要枚举所有可能的长为k的模板理论上可以是任意由26个小写字母组成的字符串找出那个能使总修改次数最小的。2.3 关键约束与洞察整除性检查这是第一道关卡。如果n % k ! 0游戏结束直接返回-1。很多粗心的选手会忘记这一步。模板的本质我们不需要真的去枚举所有26^k种可能的字符串那是个天文数字。这里有一个至关重要的洞察对于最终那个最优的模板它的第i个位置0 i k上的字符应该等于原字符串中所有“对应位置”上出现次数最多的那个字符。什么是“对应位置”我们把原字符串按长度k分组后所有分组的第i个字符它们的位置在原字符串中的索引满足i, ik, i2k, ...。这些字符构成了一个“列”。例如上面例子中k3第0列字符S[0]‘a‘,S[3]‘b‘,S[6]‘b‘- 字符集{‘a‘, ‘b‘, ‘b‘}第1列字符S[1]‘b‘,S[4]‘c‘,S[7]‘a‘- 字符集{‘b‘, ‘c‘, ‘a‘}第2列字符S[2]‘a‘,S[5]‘a‘,S[8]‘b‘- 字符集{‘a‘, ‘a‘, ‘b‘}贪心策略对于每一列如果我们选择该列中出现次数最多的字符作为模板在该位置的字符那么为了将这一列的所有字符都统一成模板字符需要修改的次数就是(分组数 - 该字符的出现次数)。因为出现次数最多的字符需要改动的其他字符最少。独立性各个列之间是相互独立的第i列选择什么字符作为模板完全不影响第j列的选择。因此我们可以对每一列单独处理将每一列的最小修改次数相加就得到了全局的最小修改次数。基于以上洞察我们成功地将一个看似需要枚举海量模板的问题简化为了对k个独立的“列”进行统计分析的问题。时间复杂度从指数级降低到了线性级。3. 算法设计与核心实现步骤有了清晰的数学模型接下来就是把它翻译成代码。我们的算法可以清晰地分为几个步骤。3.1 整体算法流程输入与校验读入字符串S和整数k。计算字符串长度n。如果n % k ! 0输出-1并结束。确定分组数groupNum n / k。这表示字符串被分成了多少组。按列统计字符频率我们需要一个大小为k的“列”的集合。对于每一列i(0 i k)我们关心的是所有索引为i, ik, i2k, ...的字符。为每一列维护一个频率数组freq[26]记录该列中‘a‘到‘z‘每个字符出现的次数。计算每一列的最小修改成本遍历第i列的频率数组freq找到出现次数最多的那个字符的频次maxFreq。要将这一列的所有字符统一最少需要修改的次数是groupNum - maxFreq。因为maxFreq个字符已经是对的剩下的groupNum - maxFreq个需要修改。累加总成本将k列的最小修改成本相加得到最终答案。输出结果。3.2 为什么是贪心证明一下可能会有人问每一列都选出现次数最多的字符这样拼出来的模板真的能保证全局修改次数最少吗是的这是一个经典的贪心选择并且可以证明其正确性。最优子结构最终的总修改次数是每一列修改次数的和。而每一列的修改次数只取决于该列选择的模板字符与其他列无关。因此全局最优解必然由每一列的最优解组成。贪心选择性质对于单独一列假设有m个字符。如果我们选择的模板字符在该列出现了x次那么修改次数就是m - x。为了使m - x最小就需要x最大。所以选择出现次数最多的字符就是当前列的最优选择。由于各列独立所以每一列都做出局部最优选择组合起来就是全局最优解。3.3 时间复杂度分析设字符串长度为n重复单元长度为k分组数m n/k。我们需要遍历字符串一次来填充k个频率数组。遍历的字符总数是n。对于每个字符我们将其计入对应列的频率数组操作是O(1)。最后我们需要遍历k个频率数组每个长度26找到最大值。这步操作是O(k * 26)。总时间复杂度为O(n k)由于26是常数且k n所以可以简化为O(n)。这完全能够应对蓝桥杯比赛中n高达10^5的数据规模。空间复杂度方面我们需要k个长度为26的整型数组即O(k)的空间同样在可接受范围内。4. Java代码实现与逐行解读理论讲完了是时候上代码了。下面是我在多次调试和优化后沉淀下来的Java实现附上了详细的注释。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); // 读取重复单元长度 k int k sc.nextInt(); // 读取字符串 SnextLine() 前用 next() 或额外 nextLine() 消费换行符 sc.nextLine(); // 消费掉 nextInt() 后的换行符 String s sc.nextLine(); int n s.length(); // 1. 整除性检查 if (n % k ! 0) { System.out.println(-1); return; } int groupNum n / k; // 总共的组数 int ans 0; // 总修改次数 // 2. 按列统计字符出现次数 // 共有 k 列每列用一个长度为26的数组统计 a-z 的出现次数 int[][] freq new int[k][26]; for (int i 0; i n; i) { char c s.charAt(i); int col i % k; // 计算当前字符属于哪一列 freq[col][c - a]; // 对应列的对应字符计数加一 } // 3. 计算每一列的最小修改次数并累加 for (int col 0; col k; col) { int maxCountInCol 0; // 遍历该列的频率数组找出出现次数最多的字符的频次 for (int ch 0; ch 26; ch) { if (freq[col][ch] maxCountInCol) { maxCountInCol freq[col][ch]; } } // 该列需要修改的次数 总组数 - 最大频次 ans (groupNum - maxCountInCol); } // 4. 输出结果 System.out.println(ans); sc.close(); } }关键代码段解读与避坑点输入处理 (sc.nextLine()): 这是一个经典的坑点。在使用了sc.nextInt()读取整数k之后输入流中会留下一个换行符‘\n‘。如果紧接着使用sc.nextLine()去读取字符串它会先读到这个换行符从而得到一个空字符串。所以必须在nextInt()后加一句sc.nextLine()来“消费”掉这个换行符。这是很多新手容易忽略的地方在竞赛中会导致莫名其妙的错误。整除性检查的提前返回: 一旦发现n % k ! 0直接输出-1并return结束程序。这避免了后续不必要的计算也符合题目要求。二维数组freq的设计:freq[col][charIndex]表示第col列中字符(char)(‘a‘ charIndex)出现的次数。这个设计将“列”作为第一维度非常直观地对应了我们的算法逻辑。核心统计循环for (int i 0; i n; i):int col i % k: 这是计算列索引的魔法公式。它完美地将原字符串索引i映射到了0到k-1的列号上。i0, k, 2k...对应第0列i1, k1, 2k1...对应第1列以此类推。freq[col][c - ‘a‘]:c - ‘a‘将字符‘a‘-‘z‘映射到数字0-25作为频率数组的索引。这一步是O(1)操作。计算最小修改次数: 对于每一列我们只关心出现次数的最大值maxCountInCol。该列的最小修改次数就是groupNum - maxCountInCol。这里不需要知道是哪个字符出现了最多次只需要知道次数。5. 测试用例与边界情况分析再好的算法也需要经过各种刁钻用例的考验。下面我们设计几组测试数据来验证代码的健壮性。5.1 常规测试用例用例1:k3,S“ababcabab“预期输出4 (我们之前手算的结果)验证我们的算法是否与手动分析一致。用例2:k2,S“aaaaaa“字符串已经是重复的(“aa“重复3次)。第0列:{‘a‘, ‘a‘, ‘a‘},maxFreq3, 修改次数0。第1列:{‘a‘, ‘a‘, ‘a‘},maxFreq3, 修改次数0。总修改次数 0。符合预期无需修改。用例3:k4,S“abcdefgh“每组字符都完全不同groupNum2。每一列的两个字符都互不相同所以maxFreq1。每一列修改次数 2 - 1 1。总修改次数 4 * 1 4。这意味着至少改4个字符比如改成“aaaa“重复或“abcd“重复。5.2 边界与特殊测试用例用例4 (整除性检查):k5,S“abcde“(n5, 能整除)groupNum1。只有一组那么每一列都只有一个字符maxFreq1。每一列修改次数 1 - 1 0。总修改次数 0。因为一组本身就是一个完整的重复单元无需修改。用例5 (整除性检查):k4,S“abc“(n3, 不能整除)预期输出-1。代码应在开始就判断并返回。用例6 (最小规模):k1,S“a“n1,groupNum1。只有一列。该列maxFreq1修改次数0。输出0。这意味着单个字符本身就是任意长度的重复串。用例7 (全相同字符):k10,S“aaaaaaaaaa“(n10)已经是完美的重复串。每一列的字符都相同maxFreq groupNum 1。总修改次数 0。用例8 (大规模随机数据): 可以自己写个循环生成一个长字符串和随机的k(保证能整除)用我们的程序计算并与一个简单的暴力枚举程序仅用于小数据验证的结果对比确保算法正确性。5.3 调试技巧如何验证中间结果在竞赛或开发中如果对结果有疑虑可以在代码中关键位置添加打印语句来调试。// ... 统计完freq后可以打印出来看看 for (int col 0; col k; col) { System.out.print(“Column “ col “: “); for (int ch 0; ch 26; ch) { if (freq[col][ch] 0) { System.out.print((char)(‘a‘ ch) “-“ freq[col][ch] “ “); } } System.out.println(); } // ... 计算maxCountInCol和ans时也可以打印通过观察每一列的字符分布可以直观地理解算法是如何工作的以及计算出的修改次数是否合理。6. 性能优化与进阶思考虽然我们当前的O(n)算法已经足够应对竞赛但总有一些场景或变种题目需要我们思考得更深。这里分享一些可能的优化点和相关的进阶思考。6.1 空间优化我们使用了int[k][26]的二维数组。如果k非常大比如接近n这个空间开销是O(k)。在某些内存极其受限的环境下虽然蓝桥杯一般不会我们可以进行优化。优化思路我们真的需要同时保留所有列的统计信息吗不需要。我们可以一列一列地处理。优化实现外层循环遍历列col(0 到 k-1)。对于每一列初始化一个长度为26的一维数组colFreq并遍历该列的所有字符索引为col, colk, col2k, ...进行统计。找到该列的maxFreq计算修改次数并累加到答案。处理下一列时复用或重新初始化colFreq数组。优劣分析优点空间复杂度从O(k)降为O(1)(如果复用数组) 或O(26)。缺点时间复杂度不变但可能因为多次遍历字符串实际上是跳着遍历而导致缓存不友好在某些情况下可能比一次性遍历慢。对于竞赛O(k)的空间通常不是瓶颈所以原始的二维数组方法更清晰、直观代码也更简洁。6.2 变种问题如果允许任意位置插入/删除字符呢原题只允许修改字符。如果规则变得更复杂比如允许插入或删除字符问题就变成了一个“编辑距离”或“字符串对齐”问题的变种难度会大大增加。你可能需要用到动态规划来求解定义dp[i][j]表示考虑原串前i个字符匹配到模板串前j个字符所需的最小编辑代价。这完全是另一个层面的问题了。6.3 与“周期串”问题的联系经典的周期串判断问题是给定字符串S判断是否存在一个长度k的子串T使得S由T重复连接而成。我们的问题可以看作是周期串问题的“宽松版”我们允许通过修改字符来“凑”出一个周期串并追求最小的修改代价。因此周期串判断算法如KMP求next数组的思想虽然不能直接套用但其中关于“前缀-后缀”匹配的洞察有时能启发我们解决更复杂的字符串近似周期问题。6.4 贪心算法的证明再思考我们之前简要证明了贪心的正确性。一个更严谨的证明可以采用“反证法”假设对于某一列不选择出现次数最多的字符char_max能得到更优的全局解。那么在该列选择其他字符char_other会导致该列的修改次数至少比选择char_max多1。由于各列独立这个“更劣”的选择无法在其他列得到补偿因为其他列的最优解是固定的因此全局解必然更差。这与假设矛盾。所以贪心策略是正确的。7. 竞赛实战技巧与避坑指南结合蓝桥杯的赛场环境我总结了几条针对此类题目的实战经验。7.1 读题与建模阶段手动画例子不要只看题目描述。像本文第二节那样自己构造一个小的、具体的例子比如k3, S“ababcabab“在纸上模拟一下过程。这个过程能极大地帮助你理解题意并可能直接启发你找到像“按列统计”这样的关键洞察。注意数据范围蓝桥杯题目描述中有时会给出n和k的范围。比如n 10^5。看到这个你就要立刻意识到O(n^2)的暴力枚举所有子串作为模板的算法是不可行的必须寻找O(n log n)或O(n)的解法。这直接引导你走向贪心或更高效的算法。识别经典模型“最小修改次数使得字符串具有某种周期性”这是一个已知的贪心模型。有经验的选手看到“重复”、“周期”、“最小修改”等关键词应该能快速联想到按模k分组统计的思路。7.2 编码与调试阶段变量命名清晰像groupNum,freq,maxCountInCol这样的变量名比简单的gn,f,mx要好得多。在紧张的竞赛中清晰的命名能减少思维负担和出错概率。重视边界条件整除性检查、k1、n0如果允许空串、全相同字符等情况一定要单独考虑并测试。很多错误都发生在边界上。使用调试输出在最终提交前可以通过注释掉调试打印语句或者使用if (DEBUG)这样的标志来控制。在本地测试时打开调试输出能帮你快速定位逻辑错误。测试用例设计不要只测题目给的样例。自己设计如第5节提到的各种边界用例和随机用例进行测试。一个简单的对拍程序你的高效算法 vs 一个保证正确但很慢的暴力算法在小数据上对比结果是发现隐蔽错误的利器。7.3 一个容易忽略的“坑”字符集范围题目通常会说“只包含小写字母”所以我们用大小为26的数组是没问题的。但如果题目说“包含大小写字母和数字”那我们的频率数组大小就需要扩大到62。更一般地如果字符集范围很大比如Unicode使用数组就不合适了应该使用HashMapCharacter, Integer来统计频率。虽然HashMap的常数时间操作稍慢但能处理任意字符集。在竞赛中务必看清题目对字符范围的描述。这道“重复字符串”的题目很好地考察了选手将实际问题抽象为数学模型的能力、对贪心策略的理解以及细致的编码实现。它不像一些难题那样需要高深的算法知识但想要快速、准确、无bug地完成也需要扎实的基本功和清晰的思路。希望这篇详细的拆解能帮助你在遇到类似问题时能够一眼看穿本质稳、准、快地写出AC代码。 蓝桥杯重复字符串问题：贪心算法与按列统计的O(n)解法
1. 问题背景与核心诉求看到“重复字符串”这个题目很多参加过蓝桥杯或者正在备赛的朋友可能会心一笑或者眉头一皱。这题出自2020年第十一届蓝桥杯国赛算是那届比赛里一道比较有代表性的字符串处理题。它不像动态规划那样需要复杂的状态推导也不像图论那样需要精巧的建模但恰恰是这种“看起来简单”的题目最容易让选手在考场上栽跟头——要么是题意理解偏差要么是边界条件没处理好要么就是算法复杂度没算对导致大规模数据超时。这道题的核心是给定一个字符串要求我们通过修改最少的字符使得这个字符串可以由某个长度为k的子串重复若干次构成。换句话说我们要找到一个“模板”子串把原字符串尽可能多地“对齐”到这个模板上修改那些对不齐的字符。这听起来有点像“周期串”的判断但加上了“允许修改”的操作并且要求修改次数最少一下子就变成了一个最优化问题。我当年第一次做这题时第一反应是暴力枚举所有可能的子串作为模板然后去计算修改成本。这个思路方向是对的但如果没有经过优化对于长度上千的字符串计算量会非常恐怖在竞赛1秒的时间限制内根本跑不完。后来经过反复推敲和测试才找到了那个既直观又高效的解法。今天我就把自己踩过的坑、优化的思路以及完整的Java实现代码毫无保留地分享出来。无论你是正在备赛蓝桥杯还是想巩固字符串和贪心算法这篇文章都能给你带来实实在在的收获。2. 题意深度拆解与数学模型建立拿到题目第一步永远是彻底读懂题意。我们先把抽象的描述转化成具体的数学和逻辑模型。2.1 问题重述假设我们有一个字符串S其长度为n。同时给定一个整数k这个k是我们要寻找的重复单元的长度。题目要求是判断能否将字符串S划分为n / k个连续的长度为k的子串这里隐含n必须能被k整除否则直接无解并且通过修改其中某些位置的字符使得这n / k个子串变得完全相同。我们的目标不是真的去修改字符串而是计算出达成上述目标所需的最少修改次数。如果n不能被k整除则直接输出-1表示无法通过修改达成“重复字符串”。2.2 一个具体例子假设S “ababcabab”,k 3。字符串长度n 99 / 3 3可以分成3个长度为3的子串“aba”,“bca”,“bab”。现在我们需要找到一个长度为3的理想模板比如“aba”。将三个子串与“aba”对比子串1:“aba”- 完全相同修改0次。子串2:“bca”- 位置0的‘b‘需改为‘a‘位置1的‘c‘需改为‘b‘位置2的‘a‘已是‘a‘。共修改2次。子串3:“bab”- 位置0的‘b‘需改为‘a‘位置2的‘b‘需改为‘a‘。共修改2次。总修改次数 0 2 2 4。但“aba”是最优模板吗不一定。我们需要枚举所有可能的长为k的模板理论上可以是任意由26个小写字母组成的字符串找出那个能使总修改次数最小的。2.3 关键约束与洞察整除性检查这是第一道关卡。如果n % k ! 0游戏结束直接返回-1。很多粗心的选手会忘记这一步。模板的本质我们不需要真的去枚举所有26^k种可能的字符串那是个天文数字。这里有一个至关重要的洞察对于最终那个最优的模板它的第i个位置0 i k上的字符应该等于原字符串中所有“对应位置”上出现次数最多的那个字符。什么是“对应位置”我们把原字符串按长度k分组后所有分组的第i个字符它们的位置在原字符串中的索引满足i, ik, i2k, ...。这些字符构成了一个“列”。例如上面例子中k3第0列字符S[0]‘a‘,S[3]‘b‘,S[6]‘b‘- 字符集{‘a‘, ‘b‘, ‘b‘}第1列字符S[1]‘b‘,S[4]‘c‘,S[7]‘a‘- 字符集{‘b‘, ‘c‘, ‘a‘}第2列字符S[2]‘a‘,S[5]‘a‘,S[8]‘b‘- 字符集{‘a‘, ‘a‘, ‘b‘}贪心策略对于每一列如果我们选择该列中出现次数最多的字符作为模板在该位置的字符那么为了将这一列的所有字符都统一成模板字符需要修改的次数就是(分组数 - 该字符的出现次数)。因为出现次数最多的字符需要改动的其他字符最少。独立性各个列之间是相互独立的第i列选择什么字符作为模板完全不影响第j列的选择。因此我们可以对每一列单独处理将每一列的最小修改次数相加就得到了全局的最小修改次数。基于以上洞察我们成功地将一个看似需要枚举海量模板的问题简化为了对k个独立的“列”进行统计分析的问题。时间复杂度从指数级降低到了线性级。3. 算法设计与核心实现步骤有了清晰的数学模型接下来就是把它翻译成代码。我们的算法可以清晰地分为几个步骤。3.1 整体算法流程输入与校验读入字符串S和整数k。计算字符串长度n。如果n % k ! 0输出-1并结束。确定分组数groupNum n / k。这表示字符串被分成了多少组。按列统计字符频率我们需要一个大小为k的“列”的集合。对于每一列i(0 i k)我们关心的是所有索引为i, ik, i2k, ...的字符。为每一列维护一个频率数组freq[26]记录该列中‘a‘到‘z‘每个字符出现的次数。计算每一列的最小修改成本遍历第i列的频率数组freq找到出现次数最多的那个字符的频次maxFreq。要将这一列的所有字符统一最少需要修改的次数是groupNum - maxFreq。因为maxFreq个字符已经是对的剩下的groupNum - maxFreq个需要修改。累加总成本将k列的最小修改成本相加得到最终答案。输出结果。3.2 为什么是贪心证明一下可能会有人问每一列都选出现次数最多的字符这样拼出来的模板真的能保证全局修改次数最少吗是的这是一个经典的贪心选择并且可以证明其正确性。最优子结构最终的总修改次数是每一列修改次数的和。而每一列的修改次数只取决于该列选择的模板字符与其他列无关。因此全局最优解必然由每一列的最优解组成。贪心选择性质对于单独一列假设有m个字符。如果我们选择的模板字符在该列出现了x次那么修改次数就是m - x。为了使m - x最小就需要x最大。所以选择出现次数最多的字符就是当前列的最优选择。由于各列独立所以每一列都做出局部最优选择组合起来就是全局最优解。3.3 时间复杂度分析设字符串长度为n重复单元长度为k分组数m n/k。我们需要遍历字符串一次来填充k个频率数组。遍历的字符总数是n。对于每个字符我们将其计入对应列的频率数组操作是O(1)。最后我们需要遍历k个频率数组每个长度26找到最大值。这步操作是O(k * 26)。总时间复杂度为O(n k)由于26是常数且k n所以可以简化为O(n)。这完全能够应对蓝桥杯比赛中n高达10^5的数据规模。空间复杂度方面我们需要k个长度为26的整型数组即O(k)的空间同样在可接受范围内。4. Java代码实现与逐行解读理论讲完了是时候上代码了。下面是我在多次调试和优化后沉淀下来的Java实现附上了详细的注释。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); // 读取重复单元长度 k int k sc.nextInt(); // 读取字符串 SnextLine() 前用 next() 或额外 nextLine() 消费换行符 sc.nextLine(); // 消费掉 nextInt() 后的换行符 String s sc.nextLine(); int n s.length(); // 1. 整除性检查 if (n % k ! 0) { System.out.println(-1); return; } int groupNum n / k; // 总共的组数 int ans 0; // 总修改次数 // 2. 按列统计字符出现次数 // 共有 k 列每列用一个长度为26的数组统计 a-z 的出现次数 int[][] freq new int[k][26]; for (int i 0; i n; i) { char c s.charAt(i); int col i % k; // 计算当前字符属于哪一列 freq[col][c - a]; // 对应列的对应字符计数加一 } // 3. 计算每一列的最小修改次数并累加 for (int col 0; col k; col) { int maxCountInCol 0; // 遍历该列的频率数组找出出现次数最多的字符的频次 for (int ch 0; ch 26; ch) { if (freq[col][ch] maxCountInCol) { maxCountInCol freq[col][ch]; } } // 该列需要修改的次数 总组数 - 最大频次 ans (groupNum - maxCountInCol); } // 4. 输出结果 System.out.println(ans); sc.close(); } }关键代码段解读与避坑点输入处理 (sc.nextLine()): 这是一个经典的坑点。在使用了sc.nextInt()读取整数k之后输入流中会留下一个换行符‘\n‘。如果紧接着使用sc.nextLine()去读取字符串它会先读到这个换行符从而得到一个空字符串。所以必须在nextInt()后加一句sc.nextLine()来“消费”掉这个换行符。这是很多新手容易忽略的地方在竞赛中会导致莫名其妙的错误。整除性检查的提前返回: 一旦发现n % k ! 0直接输出-1并return结束程序。这避免了后续不必要的计算也符合题目要求。二维数组freq的设计:freq[col][charIndex]表示第col列中字符(char)(‘a‘ charIndex)出现的次数。这个设计将“列”作为第一维度非常直观地对应了我们的算法逻辑。核心统计循环for (int i 0; i n; i):int col i % k: 这是计算列索引的魔法公式。它完美地将原字符串索引i映射到了0到k-1的列号上。i0, k, 2k...对应第0列i1, k1, 2k1...对应第1列以此类推。freq[col][c - ‘a‘]:c - ‘a‘将字符‘a‘-‘z‘映射到数字0-25作为频率数组的索引。这一步是O(1)操作。计算最小修改次数: 对于每一列我们只关心出现次数的最大值maxCountInCol。该列的最小修改次数就是groupNum - maxCountInCol。这里不需要知道是哪个字符出现了最多次只需要知道次数。5. 测试用例与边界情况分析再好的算法也需要经过各种刁钻用例的考验。下面我们设计几组测试数据来验证代码的健壮性。5.1 常规测试用例用例1:k3,S“ababcabab“预期输出4 (我们之前手算的结果)验证我们的算法是否与手动分析一致。用例2:k2,S“aaaaaa“字符串已经是重复的(“aa“重复3次)。第0列:{‘a‘, ‘a‘, ‘a‘},maxFreq3, 修改次数0。第1列:{‘a‘, ‘a‘, ‘a‘},maxFreq3, 修改次数0。总修改次数 0。符合预期无需修改。用例3:k4,S“abcdefgh“每组字符都完全不同groupNum2。每一列的两个字符都互不相同所以maxFreq1。每一列修改次数 2 - 1 1。总修改次数 4 * 1 4。这意味着至少改4个字符比如改成“aaaa“重复或“abcd“重复。5.2 边界与特殊测试用例用例4 (整除性检查):k5,S“abcde“(n5, 能整除)groupNum1。只有一组那么每一列都只有一个字符maxFreq1。每一列修改次数 1 - 1 0。总修改次数 0。因为一组本身就是一个完整的重复单元无需修改。用例5 (整除性检查):k4,S“abc“(n3, 不能整除)预期输出-1。代码应在开始就判断并返回。用例6 (最小规模):k1,S“a“n1,groupNum1。只有一列。该列maxFreq1修改次数0。输出0。这意味着单个字符本身就是任意长度的重复串。用例7 (全相同字符):k10,S“aaaaaaaaaa“(n10)已经是完美的重复串。每一列的字符都相同maxFreq groupNum 1。总修改次数 0。用例8 (大规模随机数据): 可以自己写个循环生成一个长字符串和随机的k(保证能整除)用我们的程序计算并与一个简单的暴力枚举程序仅用于小数据验证的结果对比确保算法正确性。5.3 调试技巧如何验证中间结果在竞赛或开发中如果对结果有疑虑可以在代码中关键位置添加打印语句来调试。// ... 统计完freq后可以打印出来看看 for (int col 0; col k; col) { System.out.print(“Column “ col “: “); for (int ch 0; ch 26; ch) { if (freq[col][ch] 0) { System.out.print((char)(‘a‘ ch) “-“ freq[col][ch] “ “); } } System.out.println(); } // ... 计算maxCountInCol和ans时也可以打印通过观察每一列的字符分布可以直观地理解算法是如何工作的以及计算出的修改次数是否合理。6. 性能优化与进阶思考虽然我们当前的O(n)算法已经足够应对竞赛但总有一些场景或变种题目需要我们思考得更深。这里分享一些可能的优化点和相关的进阶思考。6.1 空间优化我们使用了int[k][26]的二维数组。如果k非常大比如接近n这个空间开销是O(k)。在某些内存极其受限的环境下虽然蓝桥杯一般不会我们可以进行优化。优化思路我们真的需要同时保留所有列的统计信息吗不需要。我们可以一列一列地处理。优化实现外层循环遍历列col(0 到 k-1)。对于每一列初始化一个长度为26的一维数组colFreq并遍历该列的所有字符索引为col, colk, col2k, ...进行统计。找到该列的maxFreq计算修改次数并累加到答案。处理下一列时复用或重新初始化colFreq数组。优劣分析优点空间复杂度从O(k)降为O(1)(如果复用数组) 或O(26)。缺点时间复杂度不变但可能因为多次遍历字符串实际上是跳着遍历而导致缓存不友好在某些情况下可能比一次性遍历慢。对于竞赛O(k)的空间通常不是瓶颈所以原始的二维数组方法更清晰、直观代码也更简洁。6.2 变种问题如果允许任意位置插入/删除字符呢原题只允许修改字符。如果规则变得更复杂比如允许插入或删除字符问题就变成了一个“编辑距离”或“字符串对齐”问题的变种难度会大大增加。你可能需要用到动态规划来求解定义dp[i][j]表示考虑原串前i个字符匹配到模板串前j个字符所需的最小编辑代价。这完全是另一个层面的问题了。6.3 与“周期串”问题的联系经典的周期串判断问题是给定字符串S判断是否存在一个长度k的子串T使得S由T重复连接而成。我们的问题可以看作是周期串问题的“宽松版”我们允许通过修改字符来“凑”出一个周期串并追求最小的修改代价。因此周期串判断算法如KMP求next数组的思想虽然不能直接套用但其中关于“前缀-后缀”匹配的洞察有时能启发我们解决更复杂的字符串近似周期问题。6.4 贪心算法的证明再思考我们之前简要证明了贪心的正确性。一个更严谨的证明可以采用“反证法”假设对于某一列不选择出现次数最多的字符char_max能得到更优的全局解。那么在该列选择其他字符char_other会导致该列的修改次数至少比选择char_max多1。由于各列独立这个“更劣”的选择无法在其他列得到补偿因为其他列的最优解是固定的因此全局解必然更差。这与假设矛盾。所以贪心策略是正确的。7. 竞赛实战技巧与避坑指南结合蓝桥杯的赛场环境我总结了几条针对此类题目的实战经验。7.1 读题与建模阶段手动画例子不要只看题目描述。像本文第二节那样自己构造一个小的、具体的例子比如k3, S“ababcabab“在纸上模拟一下过程。这个过程能极大地帮助你理解题意并可能直接启发你找到像“按列统计”这样的关键洞察。注意数据范围蓝桥杯题目描述中有时会给出n和k的范围。比如n 10^5。看到这个你就要立刻意识到O(n^2)的暴力枚举所有子串作为模板的算法是不可行的必须寻找O(n log n)或O(n)的解法。这直接引导你走向贪心或更高效的算法。识别经典模型“最小修改次数使得字符串具有某种周期性”这是一个已知的贪心模型。有经验的选手看到“重复”、“周期”、“最小修改”等关键词应该能快速联想到按模k分组统计的思路。7.2 编码与调试阶段变量命名清晰像groupNum,freq,maxCountInCol这样的变量名比简单的gn,f,mx要好得多。在紧张的竞赛中清晰的命名能减少思维负担和出错概率。重视边界条件整除性检查、k1、n0如果允许空串、全相同字符等情况一定要单独考虑并测试。很多错误都发生在边界上。使用调试输出在最终提交前可以通过注释掉调试打印语句或者使用if (DEBUG)这样的标志来控制。在本地测试时打开调试输出能帮你快速定位逻辑错误。测试用例设计不要只测题目给的样例。自己设计如第5节提到的各种边界用例和随机用例进行测试。一个简单的对拍程序你的高效算法 vs 一个保证正确但很慢的暴力算法在小数据上对比结果是发现隐蔽错误的利器。7.3 一个容易忽略的“坑”字符集范围题目通常会说“只包含小写字母”所以我们用大小为26的数组是没问题的。但如果题目说“包含大小写字母和数字”那我们的频率数组大小就需要扩大到62。更一般地如果字符集范围很大比如Unicode使用数组就不合适了应该使用HashMapCharacter, Integer来统计频率。虽然HashMap的常数时间操作稍慢但能处理任意字符集。在竞赛中务必看清题目对字符范围的描述。这道“重复字符串”的题目很好地考察了选手将实际问题抽象为数学模型的能力、对贪心策略的理解以及细致的编码实现。它不像一些难题那样需要高深的算法知识但想要快速、准确、无bug地完成也需要扎实的基本功和清晰的思路。希望这篇详细的拆解能帮助你在遇到类似问题时能够一眼看穿本质稳、准、快地写出AC代码。