0466. Count The Repetitions¶
题目信息¶
- 题号:
0466
- 难度:
Hard
- 主题:
重复字符串、子序列、重复块、最大次数
- 原题:
- 重点:
[s,n]表示字符串重复拼接、目标通过删除字符形成、字符顺序必须保留、返回完整目标块数量
题目重述¶
定义 [s, n] 为把字符串 s 连续拼接 n 次。给定 s1、n1、s2、n2,令 S1 = [s1, n1]、S2 = [s2, n2]。返回最大的整数 m,使 [S2, m] 是 S1 的子序列。
子序列可以从 S1 中删除任意字符,但保留字符的相对顺序不能改变;不要求字符连续。s1 和 s2 长度位于 [1, 100],只包含小写英文字母;n1 和 n2 位于 [1, 10^6]。返回值表示能够完整匹配多少个 S2 块,不能把不足一整块的剩余匹配计入。
自建示例¶
每个源块都贡献一个目标子序列:
输入:s1 = "abc",n1 = 3,s2 = "ac",n2 = 1
输出:3
解释:S1 为 abcabcabc,可以从每个 abc 中按顺序选出 ac,因此能够形成三个完整的 S2。
目标含源串中不存在的字符:
输入:s1 = "ab",n1 = 5,s2 = "ac",n2 = 1
输出:0
解释:S1 中没有字符 c,连一个完整的 ac 都无法形成。
在每个源块边界寻找相同状态¶
扫描一个 s1 块时,顺次匹配 s2 的字符;每次指针走过 s2 尾部,就完成一个目标块并从 s2[0] 重新开始。一个源块扫描结束时,状态只由“下次要匹配 s2 的哪个位置”和“已经完成了多少个目标块”组成。
状态位置只有 |s2| 种。若在两个不同的源块边界再次看到同一个位置,之间的源块序列会重复,完成目标块的增量也固定,可以把剩余的 s1 块按周期整段跳过。最后用能够匹配出的 s2 块数除以 n2,得到完整 [s2,n2] 的数量。
C++ 实现¶
class Solution {
public:
int getMaxRepetitions(std::string s1, int n1,
std::string s2, int n2) {
std::vector<int> firstBlock(s2.size(), -1);
std::vector<long long> firstCompleted(s2.size(), 0);
int position = 0;
int block = 0;
long long completed = 0;
while (block < n1) {
for (char character : s1) {
if (character != s2[position]) continue;
++position;
if (position == static_cast<int>(s2.size())) {
position = 0;
++completed;
}
}
++block;
if (firstBlock[position] == -1) {
firstBlock[position] = block;
firstCompleted[position] = completed;
} else {
int cycleBlocks = block - firstBlock[position];
long long cycleCompleted =
completed - firstCompleted[position];
long long cycles = (n1 - block) / cycleBlocks;
block += static_cast<int>(cycles * cycleBlocks);
completed += cycles * cycleCompleted;
}
}
return static_cast<int>(completed / n2);
}
};
代码分析¶
只在源块边界记录状态,避免把周期切在一个 s1 块内部;再次到达同一匹配位置时,周期内的完成数量可整体相加,覆盖 n1 达到百万级的情况。每个状态首次记录一次,之后至多处理剩余周期外的块,时间复杂度为 O(|s1| * |s2|) 的状态扫描量,额外空间复杂度为 O(|s2|)。