刷 LeetCode 的时候很多人会被 466 这道题卡住。题目标题写得很清楚统计重复个数函数签名是getMaxRepetitions(String s1, int n1, String s2, int n2)。给定 s1、s2 以及各自重复次数 n1、n2要你返回一个最大整数 m使得s2重复n2次得到的字符串再重复m次之后仍然能作为s1重复n1次得到的字符串的子序列。我第一次做的时候直接拼字符串遇到大 n1 的用例直接爆内存。后来仔细分析才发现这题真正考的是“周期性”和字符串拼接没有关系。这篇文章我会把 LeetCode 466 从读题到实现完整拆开重点讲清楚为什么可以用循环节加速、Java 代码每一行在干什么、以及几个很容易踩的坑。适合准备算法面试的 Java 开发也适合刷题时卡在这一题上想找“人能听懂”的解法的人。1. 先读懂题目到底在统计什么1.1 题面到底让你算什么题目里定义了一个记号[s, n]表示把字符串 s 连续重复 n 次。比如[acb, 3]得到的就是acbacbacb。再往下看getMaxRepetitions就是让你算在S1 [s1, n1]这个长串里最多能按顺序取出多少个完整的S2 [s2, n2]。注意这里不是问你能匹配多少个子串而是问你能匹配多少个子序列。子序列允许跳着选字符只要字符出现的先后顺序能对上就没问题。因为题目原文里说的是“remove some characters”这类表述所以s2的一个副本并不要求在原串里连续出现。很多人一开始把它当成连续子串做越做越懵就是这个原因。举个例子s1 acb, n1 4, s2 ab, n2 2。这里S1 acbacbacbacbS2 abab。正确答案是 2表示能在S1中按顺序取出两个S2也就是选出来的字符序列是abababab。注意看S1里的a和b中间永远隔着c但你仍然可以先取a再跳过c取b所以它是子序列匹配不是连续子串匹配。1.2 为什么不能把字符串真的拼出来很多人第一反应是模拟把s1重复 n1 次得到一个大字符串再把s2重复 n2 次得到另一个大字符串然后暴力找。这在数据小的时候没问题但 LeetCode 会给很大的 n1比如几十万、上百万。s1本身长度可以有 100那么S1的长度可能到上亿甚至更多。别说拼接了光是创建这个大字符串就已经让内存爆掉。就算能创建出来单纯用一个双指针在超长字符串里傻扫时间复杂度也是O(len(S1) * len(S2))量级在 n1 很大的时候完全不可接受。所以这题的核心不是“模拟”而是“找规律”。你会发现s1本身是重复块s2也是重复块两个周期结构叠在一起匹配过程必然会出现周期性。把这个周期找出来就可以跳过中间大量重复的计算。1.3 子序列和连续子串不是一回事我见过很多人卡在 466 上其实是因为把子序列和子串混在一起。子串要求连续比如acb里不存在ab这个连续子串但存在ab这个子序列因为你可以取第 1 个字符a和第 3 个字符b中间跳过c。这套算法里的贪心匹配本质上就是子序列匹配。我们从s2的第 0 个字符开始在S1里从左到右扫遇到和当前需要的字符相等的字符就消费掉然后指针后移当s2匹配完一个完整副本后计数加 1指针回到 0。这个“能匹配就匹配”的策略在子序列问题里是最优的因为越早匹配一个字符后面可选的字符就越多绝对不会因为“太早匹配”而丢解。这一点和连续子串匹配完全不同连续子串里如果选错了起点还得回溯但子序列不需要。2. 核心思路不要硬扫而是找循环节2.1 一次遍历怎么统计完整 s2先把最基础的匹配逻辑写出来。假设我们在扫描S1维护一个指针idx表示当前需要匹配s2中的哪个字符。每次扫描到一个字符c如果c s2.charAt(idx)说明当前字符能用idx。如果idx已经等于s2.length()说明一个完整的s2匹配完成了计数加 1idx归零继续匹配下一个s2。这个逻辑很简单它其实是在S1中找“尽可能多”的s2副本。因为题目的最终目的是求S2能重复多少次而S2本身是由 n2 个s2组成的所以先数出S1里最多能构成多少个完整的s2最后除以 n2 就能得到答案。但问题来了如果我们把s1重复 n1 次逐块扫描每扫描一个s1块都做一次上述匹配那总工作量就是 n1 乘以s1.length()。n1 一大就完蛋。所以必须找到一种方式把大量重复的“块”一次性跳过去。2.2 记录状态s2 内部匹配到哪了注意每处理完一个完整的s1块之后我们不需要记住整个大字符串里的位置只需要记住s2内部的指针idx以及到目前为止已经匹配了多少个完整s2。为什么只需要记住idx因为s1是固定重复块每次处理一整块s1时的处理逻辑完全一样。决定下一个块匹配结果的就是当前idx从哪里开始。如果两个时刻的idx相同那么再处理相同数量的s1块idx的变化规律和matched的增长规律也会完全一致。这就好比你在一条环形轨道上走路只要脚下的位置相同你后面每一步看到的风景就一样。所以我们可以用一张哈希表把“处理完某个s1块之后的idx”作为 key把当时的“已用 s1 块数”和“已匹配 s2 数量”作为 value 存下来。等某个idx第二次出现就说明状态重复了也就是找到了循环。2.3 状态重复就是循环节出现假设处理完第a个s1块时idx是某个值 p已匹配数量是cntA。后面处理完第b个s1块时idx又变成同样的 p已匹配数量是cntB。由于从状态 p 出发处理一个s1块的规律完全一样那么从第a1块到第b块这一段就是一段稳定循环每经过b - a个s1块idx会回到 p。每经过这段循环matched会增加cntB - cntA。所以如果还剩R n1 - b个块我就能完整地跳过若干次循环完整循环次数R / (b - a)能直接加上的匹配数量完整循环次数 * (cntB - cntA)跳完之后剩下的块数一定小于b - a这部分再逐块做一次普通模拟即可。这就是整个题目的优化核心不把 n1 个块都跑完而是通过状态重复找到周期把中间重复的成百上千个块一次性算掉。2.4 循环节能省多少计算你可能担心如果一直没有出现状态重复怎么办结论是不可能一直不重复。因为idx的取值只有0到len(s2) - 1这len(s2)种可能。每处理完一个s1块我们会得到一个idx。如果连续记录了len(s2) 1个块的idx根据鸽巢原理必然有两个块的idx相同也就必然会检测出循环节。所以检测循环只需要处理大约len(s2)个s1块而不是 n1 个。每个块的处理成本是O(len(s1))因此整个算法的核心成本大约是O(len(s1) * len(s2))。相比暴力O(n1 * len(s1))这可以说是质的提升。3. Java 实现与代码拆解3.1 可直接运行的 Java 解法下面是我在 LeetCode 上验证过的 Java 实现注释写在关键位置public int getMaxRepetitions(String s1, int n1, String s2, int n2) { if (n1 0 || n2 0 || s1.isEmpty() || s2.isEmpty()) { return 0; } MapInteger, int[] seen new HashMap(); int used 0; // 已经消费掉的 s1 块数 int matched 0; // 已经匹配完的完整 s2 个数 int idx 0; // 当前要匹配 s2 中的哪个字符 boolean cycleHandled false; while (used n1) { // 处理一个完整的 s1 块 for (char c : s1.toCharArray()) { if (c s2.charAt(idx)) { idx; if (idx s2.length()) { matched; idx 0; } } } used; // 如果已经跳过循环后面就老老实实处理剩余块 if (cycleHandled) { continue; } int[] prev seen.get(idx); if (prev ! null) { int prevUsed prev[0]; int prevMatched prev[1]; int cycleUsed used - prevUsed; int cycleMatched matched - prevMatched; int remain n1 - used; int loops remain / cycleUsed; if (loops 0) { matched loops * cycleMatched; used loops * cycleUsed; } // 一旦找到循环节就不再继续记录状态 // 防止同一个循环节被重复利用。 cycleHandled true; } else { seen.put(idx, new int[]{used, matched}); } } return matched / n2; }这段代码的返回值就是题目要求的最大整数 m。你不需要真的构造出[s2, n2]只需要在S1里统计所有完整的s2副本数量最后除以 n2 并向下取整即可。3.2 变量表先弄清每个变量的含义代码里的变量不多但每个都很关键。我把它们整理成了表格方便对照。变量含义为什么需要used当前已经消费掉的s1重复块数用来判断整个S1是否已经处理完matched截止到当前能在S1中按顺序匹配出的完整s2数量最后要除以 n2 得到结果idx当前匹配到s2内部的哪个位置决定下一个s1块的匹配起点seen记录某个idx第一次出现时对应的used和matched用来检测状态重复找出循环节cycleHandled是否已经处理过循环跳跃防止跳过循环后又被同一张旧表误导其中seen为什么以idx为 key因为在匹配过程中“未来会怎样”完全取决于当前idx是什么。s1块是固定重复的只要idx一样下一个块能做多少事就一样。used和matched只影响总量不影响接下来的匹配行为所以不需要作为 key。3.3 循环跳跃的逻辑读一遍假设某一次处理完第used个块后发现seen里已经存在同一个idx说明眼前这条匹配路径正在重复过去的一段路。此时我们取出之前的记录prevUsed和prevMatched计算出循环节的大小cycleUsed used - prevUsed一个循环节消耗多少个s1块。cycleMatched matched - prevMatched一个循环节能多匹配出多少个完整的s2。然后看还剩多少块remain n1 - usedloops remain / cycleUsedloops表示在剩下的块里还能完整走多少个循环。如果能走就直接把matched加上loops * cycleMatched把used加上loops * cycleUsed相当于瞬间跳过了所有完整的循环块。跳完之后还剩remain % cycleUsed个块这些块不足一个循环只能继续老老实实用 while 循环逐块处理。所以我在代码里把cycleHandled设为 true后面的块不再记录状态避免再用旧数据去重复跳跃。3.4 时间复杂度与空间复杂度如果不优化复杂度是O(n1 * len(s1))因为每个s1块都要完整扫描一次。加入循环节后情况变得很理想找到循环节之前最多处理len(s2) 1个块。找到循环节后一次性跳过大量块。最后剩余的块数小于一个循环节而循环节长度也最多是len(s2)量级。所以整体时间复杂度可以控制在O(len(s1) * len(s2))左右。如果 n1 本身很小那就按普通逐块模拟跑复杂度也不会超过O(n1 * len(s1))。空间上主要就是一张哈希表key 是intvalue 是长度为 2 的int[]。因为idx最多只有len(s2)种取值所以哈希表大小是O(len(s2))。这个空间成本非常低。4. 边界条件、常见坑与测试用例4.1 s2 字符在 s1 里缺失如果s2里某个字符在s1中根本没有那么idx永远卡在那个位置matched永远不会增长。此时seen里也会很快出现重复的idx0或某个固定值循环节里的cycleMatched是 0跳跃多少次都不增加匹配数最终返回 0。这个行为是正确的。比如s1 abc, n1 10, s2 x, n2 3不管重复多少次S1里都找不到x答案就是 0。代码里即使触发了循环跳跃matched也不会变返回 0没问题。4.2 为什么最后要除以 n2题目要求的是[s2, n2]这个整体能重复多少次而不是问能匹配多少个单独的s2。一个[s2, n2]等于 n2 个s2连在一起所以我们必须先算出完整的s2个数再整除 n2。整除也很关键。如果S1里能匹配出 5 个完整的s2而 n2 是 2那么最多只能凑出 2 个完整的[s2, n2]因为 5 / 2 2。剩下的 1 个s2不够组成一个完整的[s2, n2]不能算数。代码里直接matched / n2整数除法自动向下取整正好符合要求。4.3 循环检测时剩余块不足怎么办有时候我们确实检测到了循环节但剩余块数remain比一个循环节cycleUsed还小。这种情况下loops是 0不能跳跃。我的处理是不跳跃但把cycleHandled置为 true然后继续用一个普通的 while 循环把剩余块处理完。有人会问既然不能跳跃为什么不让它继续循环检测考虑一下当前idx和循环起始时的idx相同再往后的状态序列会和之前那次循环完全一样。剩余块如果不够一个循环节就不可能再次碰到和旧表里一样的idx所以继续记录状态没有意义。直接顺序处理完反而是最稳妥的也避免了重复使用同一个循环节导致计数错误。4.4 最容易踩的几个坑第一个坑是把seen.put放在字符循环里面。seen记录的是“处理完一个完整s1块之后”的状态不是处理到一半的状态。如果放在字符循环里面状态太多太碎循环节反而不容易干净地出现代码也容易出 bug。第二个坑是在循环跳跃之后没有关闭循环检测。检测到循环节后如果还继续往seen里写状态后续可能用更早的旧记录再次跳跃导致matched被重复累加。这个 bug 很隐蔽我建议所有人在写完代码后专门测一个 n1 稍大、能触发多次循环的用例。第三个坑是认为idx只有到 0 时才算状态重复。其实idx可以是s2中的任意位置。只要两次处理完s1块后的idx相同就说明匹配状态重复了。即使当前只匹配到s2的一半循环节依然成立。第四个坑是忽略s2为空的边界。虽然 LeetCode 输入一般不会给空字符串但写在通用方法里还是要防御一下否则s2.charAt(idx)会直接抛异常。我的代码里一开始就做了空字符串判断。4.5 用官方示例验证一下拿官方示例一s1 acb, n1 4, s2 ab, n2 2走一遍处理第 1 个acb块a匹配ab匹配b得到一个完整s2idx回到 0matched 1。记录seen[0] {1, 1}。处理第 2 个acb块同样得到一个完整s2matched 2idx又回到 0。发现seen里已经有 0于是得到循环节cycleUsed 1cycleMatched 1。剩余块数是4 - 2 2loops 2 / 1 2直接matched 2 2 * 1 4used 4。最终matched / n2 4 / 2 2和答案一致。这个例子很典型它说明哪怕循环节长度为 1也能靠跳跃直接算出答案。5. 手算一遍完整推演两个用例5.1 示例二ab, 2, ab, 2输入是s1 ab, n1 2, s2 ab, n2 2。这时S1 ababS2 abab最多只能取 1 个S2所以正确答案是 1。用代码跑一遍处理第 1 个ab块a匹配b匹配matched 1idx 0记录seen[0] {1, 1}。处理第 2 个ab块matched 2idx 0发现重复状态。cycleUsed 1cycleMatched 1remain 0loops 0。不能跳跃cycleHandled true循环结束。返回2 / 2 1。这里注意循环检测到了但因为剩余块数是 0所以没有跳跃。这也是边界条件的一种循环节存在但不一定每次都能靠它省时间。5.2 一个循环节长度大于 1 的例子找一个s1 aab, n1 5, s2 ab, n2 1的例子。s1块是aabs2是ab。第 1 个块字符a匹配s2[0]idx 1第二个a不是b跳过b匹配matched 1idx 0。记录seen[0] {1, 1}。第 2 个块同样matched 2idx 0。检测到循环cycleUsed 1剩余5 - 2 3loops 3于是matched 2 3 * 1 5used 5。返回5 / 1 5。这个例子说明即使s1内部有两个相同的字符导致匹配过程不那么“整齐”循环节依然是稳定的。5.3 面试时怎么讲这道题如果你在面试里遇到这题我建议先讲一个最直白的暴力思路把S1和S2的完整串想成逻辑上的字符串用双指针扫统计能匹配多少个s2然后除以 n2。面试官如果追问“n1 很大怎么办”你再引出循环节优化。讲循环节时不要一上来就甩代码先说清楚状态是什么每处理完一个s1块后s2内部的匹配位置idx就是状态。因为idx的可能取值有限所以状态一定会重复状态重复后当前这轮匹配路径和上一轮完全一样因此可以跳过中间重复的s1块。这个“状态重复”的思路在很多字符串周期题里都能复用比死记这道题有价值得多。我在实际刷题中体会最深的一点是这道题最好不要一上来就想“高级算法”而是先老老实实把“一个 s1 块能怎么推进 s2 的匹配”模拟清楚再去看状态什么时候重复。只要模拟那部分写对了循环节优化就是顺理成章的事情。很多错误解法都是因为最基础的匹配指针搞错了后面优化再花哨也白搭。