LeetCode 466 统计重复个数

摘要

《统计重复个数》是一道看起来像字符串题，实际上是模式发现 + 数学加速的题。

很多人第一次写这道题，都会下意识用“模拟拼字符串”的方式，结果很快就会发现：
字符串根本拼不动，n1、n2最大是 10⁶，暴力就是在作死。

这道题真正考的不是字符串操作，而是：

• 如何把“重复结构”找出来
• 如何用一次循环，干掉成千上万次重复计算

如果你平时做过日志分析、消息消费、批量规则匹配，这道题的思路会非常熟。

描述

题目里定义了一个挺绕的概念：

str = [s, n] 表示 s 重复 n 次拼接

比如：

[s1, n1] = ["acb", 4] => "acbacbacbacb"

然后又给了一个规则：

如果可以从 s2 中删除一些字符，得到 s1，那么就说 s1 可以从 s2 获得。

注意这里是子序列，不是子串，字符顺序要对，但可以跳着删。

最终问题是：

在str1 = [s1, n1]中，最多能找出多少个完整的
str2 = [s2, n2]

换句话说：
s1重复n1次，最多能“拼”出多少组s2重复n2次。

题解答案

这道题的核心思路只有一句话：

暴力模拟一次s1，记录匹配s2的状态，一旦发现循环，就直接数学跳跃。

整体拆解成三步：

1. 模拟s1的字符流，去匹配s2
2. 记录“每次s1结束时，s2匹配到了哪里”
3. 一旦发现状态重复，说明进入循环，可以直接计算答案

这是一个非常经典的状态压缩 + 循环检测的套路。

题解代码分析

下面是完整 Swift 实现，可以直接在 LeetCode 或本地 Playground 运行。

classSolution{funcgetMaxRepetitions(_s1:String,_n1:Int,_s2:String,_n2:Int)->Int{lets1Arr=Array(s1)lets2Arr=Array(s2)letlen1=s1Arr.countletlen2=s2Arr.count// indexRecorder[i] 表示：第 i 次 s1 用完后，s2 当前匹配到的位置// countRecorder[i] 表示：第 i 次 s1 用完后，总共匹配了多少个 s2varindexRecorder=[Int](repeating:0,count:n1+1)varcountRecorder=[Int](repeating:0,count:n1+1)varindex2=0varcount2=0foriin1...n1{forcins1Arr{ifc==s2Arr[index2]{index2+=1ifindex2==len2{index2=0count2+=1}}}indexRecorder[i]=index2 countRecorder[i]=count2// 检查是否出现循环forkin0..<i{ifindexRecorder[k]==index2{// 找到循环letpreCount=countRecorder[k]letloopCount=countRecorder[i]-countRecorder[k]letloopLength=i-kletremaining=n1-kletloops=remaining/loopLengthletrest=remaining%loopLengthlettotal=preCount+loops*loopCount+(countRecorder[k+rest]-countRecorder[k])returntotal/n2}}}returncountRecorder[n1]/n2}}

关键逻辑拆解

为什么要记录index2？

index2表示：
当前s2已经匹配到了第几个字符

如果某一次s1用完后，index2和之前某次完全一样，那说明：

后面的匹配过程会一模一样
进入了“死循环”

这就和我们在实际系统里发现“消费 offset 重复”是一个道理。

为什么可以直接数学计算？

一旦进入循环：

• 每一轮循环，s1消耗固定次数
• 每一轮循环，s2增加固定个数

那剩下的就不需要一轮一轮算了，直接：

循环次数 × 每轮收益

这一步为什么这么重要？

returntotal/n2

因为题目问的是：

能拼出多少个完整的[s2, n2]

不是s2的次数，而是多少组n2

示例测试及结果

示例 1

letsolution=Solution()print(solution.getMaxRepetitions("acb",4,"ab",2))

推演一下

s1 = "acb"
s2 = "ab"

• 每一轮s1，都能匹配出一个"ab"
• n1 = 4，一共能得到 4 个"ab"
• 每2个"ab"才算一组

最终结果：

2

示例 2

print(solution.getMaxRepetitions("acb",1,"acb",1))

s1和s2完全一样，一次就够。

输出：

1

时间复杂度

• 外层最多跑n1次
• 每次扫描s1的长度（最大 100）
• 循环检测最多n1

在最坏情况下是：

O(n1 * (|s1| + n1))

但实际上由于循环很早就会出现，性能远好于理论最坏值。

空间复杂度

主要使用了两个数组：

• indexRecorder
• countRecorder

空间复杂度为：

O(n1)

在题目限制内完全可控。

总结

《统计重复个数》是一道非常值得反复琢磨的题，它教会你的不是字符串技巧，而是：

• 如何识别“重复状态”
• 如何把线性模拟升级成“数学跳跃”
• 如何避免无意义的重复计算