LeetCode 466. 统计重复个数
目录
题目描述
题意分析
题目目标：定义
str1为字符串 s1 连续重复 n1 次得到的串，str2为 s2 连续重复 n2 次得到的串。要求找出最大的整数 m，使得「str2 重复 m 次」仍然能从 str1 中通过删除若干字符得到，也就是仍然是 str1 的子序列。
核心约束：注意匹配的是子序列而不是子串，允许跳过任意字符，这让匹配过程可以用一个简单的贪心双指针完成——从左到右扫描 str1，每遇到与当前待匹配字符相同的就前进一位。第二个约束是数据规模的极端不对称：s1 和 s2 的长度都不超过 100，但 n1 可以达到 $10^6$，这意味着 str1 的总长度可达 $10^8$，逐字符扫描一遍是可行的但已经很贴边，而如果 n1 再大就完全不行。这种「短模式 + 巨量重复」的形状是循环节检测的经典信号。第三个观察是最终答案要把匹配到的 s2 个数再除以 n2，因为一份 str2 由 n2 个 s2 拼成。
边界处理：s2 中可能存在 s1 里根本没有的字符，此时一个 s2 都匹配不出来，答案为 0；n1 可能只有 1，此时循环节还来不及形成就结束了，必须有一条不依赖循环节的兜底返回；循环节可能从第一轮就开始，也可能前面有一段不进入循环的前缀，两部分要分开结算；剩余轮数做整除和取模时，基准点必须与前缀的结束位置严格对齐，差一就会整体错位。
解法：循环节检测
核心思路
逐字符匹配
s2时，贪心地遇到当前所需字符就匹配，能得到最多的完整s2。把一整轮s1看成状态转移：进入时只需知道当前匹配到s2的下标index，扫描后得到新的下标以及新增的完整匹配数。
index只有s2.length()种取值。若某一轮结束后的index曾出现过，则两次快照之间的轮数和完整s2数构成循环节；从相同状态继续扫描，未来转移与产出必然重复。哈希表记录
index -> (已处理 s1 轮数, 已匹配 s2 数)。发现循环后，将剩余轮数除以循环长度，一次跳过尽可能多的完整循环，再逐轮处理不足一个循环的尾部。不变量是：
rounds表示已经完整扫描的s1份数，matched表示这些字符中贪心匹配出的完整s2数，index表示下一次要匹配的s2位置。循环跳跃从同一index出发并回到同一index，所以不会改变后续尾部的匹配结果。最终matched / n2就是完整str2的最大重复数。
解题步骤
- 初始化
index = 0、matched = 0、rounds = 0，并记录初始快照。- 每轮扫描一次
s1，按子序列规则推进index；走完s2时归零并增加matched。- 轮末若
index首次出现，记录快照；若已出现，计算循环长度与循环产出。- 跳过剩余轮数中的完整循环，再逐轮处理尾部。
- 返回
matched / n2。
s1 = "acb", n1 = 4, s2 = "ab", n2 = 2时，每轮都完成一个s2且回到index = 0，循环长度为 1。四轮得到四个s2，即两个str2。若
s2含有s1从未出现的字符，状态会以零产出形成循环并直接跳过，答案为 0。
代码实现
import java.util.HashMap;
import java.util.Map;
class Solution {
public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
Map<Integer, long[]> seen = new HashMap<>();
seen.put(0, new long[] {0, 0});
int index = 0;
int rounds = 0;
long matched = 0;
boolean accelerated = false;
while (rounds < n1) {
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) == s2.charAt(index)) {
index++;
if (index == s2.length()) {
index = 0;
matched++;
}
}
}
rounds++;
if (!accelerated) {
long[] previous = seen.get(index);
if (previous == null) {
seen.put(index, new long[] {rounds, matched});
} else {
int cycleRounds = rounds - (int) previous[0];
long cycleMatches = matched - previous[1];
int cycles = (n1 - rounds) / cycleRounds;
rounds += cycles * cycleRounds;
matched += (long) cycles * cycleMatches;
accelerated = true;
}
}
}
return (int) (matched / n2);
}
}
type snapshot struct {
rounds int
matched int64
}
func getMaxRepetitions(s1 string, n1 int, s2 string, n2 int) int {
seen := map[int]snapshot{0: {}}
index, rounds := 0, 0
var matched int64
accelerated := false
for rounds < n1 {
for i := 0; i < len(s1); i++ {
if s1[i] == s2[index] {
index++
if index == len(s2) {
index = 0
matched++
}
}
}
rounds++
if !accelerated {
if previous, ok := seen[index]; ok {
cycleRounds := rounds - previous.rounds
cycleMatches := matched - previous.matched
cycles := (n1 - rounds) / cycleRounds
rounds += cycles * cycleRounds
matched += int64(cycles) * cycleMatches
accelerated = true
} else {
seen[index] = snapshot{rounds: rounds, matched: matched}
}
}
}
return int(matched / int64(n2))
}
复杂度分析
- 时间复杂度：$O(\min(n_1,\lvert s_2\rvert)\cdot\lvert s_1\rvert)$。循环前缀与跳跃后的尾部都受有限状态数限制。
- 空间复杂度：$O(\min(n_1,\lvert s_2\rvert))$，用于保存不同
index的快照。
关键点总结
- 每轮
s1是一个确定状态转移，完整状态只有s2的当前下标。- 相同下标再次出现，说明中间轮次与匹配产出会周期性重复。
- 循环跳跃必须同时更新已处理轮数和完整匹配数。
- 跳跃后仍需模拟不足一个循环的尾部。
- 最终统计的是
s2份数，还要除以n2才是str2份数。
易错点总结
- 把子序列匹配写成连续子串匹配；
"ab"可以从"acb"中跳过'c'得到。- 将累计匹配数纳入循环状态，会因它单调增加而永远找不到重复状态。
- 循环长度必须用两次快照的轮数差，循环产出必须用匹配数差。
- 只跳循环而不处理尾部，会漏掉剩余不足一个循环的轮次。
- 跳跃轮数计算若未扣除已处理的
rounds，会重复计算前缀。- 忘记最后除以
n2，返回的是s2数量而不是str2数量。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 392. 判断子序列 | 简单 | 本题内层匹配的最简形态，只判断一次是否为子序列，贪心双指针即可 |
| 792. 匹配子序列的单词数 | 中等 | 大量模式串对同一主串做子序列匹配，需要预处理位置表或分桶来避免重复扫描 |
| 459. 重复的子字符串 | 简单 | 同样围绕字符串的周期性，但目标是识别最小重复单元而非计数 |
| 202. 快乐数 | 简单 | 确定性状态转移下的循环检测，可用哈希记录或快慢指针，思路与本题同源 |
| 141. 环形链表 | 简单 | 循环检测的最纯粹形态，展示了用 $O(1)$ 空间替代快照数组的另一条路径 |
| 28. 找出字符串中第一个匹配项的下标 | 简单 | 换成子串匹配，考察 KMP 中前缀函数对周期结构的刻画 |