0466. Count The Repetitions
===========================
题目信息
--------
:题号: 0466
:难度: Hard
:主题: 重复字符串、子序列、重复块、最大次数
:原题: `LeetCode 0466 `_
:重点: ``[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`` 块,不能把不足一整块的剩余匹配计入。
自建示例
--------
每个源块都贡献一个目标子序列:
.. code-block:: text
输入:s1 = "abc",n1 = 3,s2 = "ac",n2 = 1
输出:3
解释:S1 为 abcabcabc,可以从每个 abc 中按顺序选出 ac,因此能够形成三个完整的 S2。
目标含源串中不存在的字符:
.. code-block:: text
输入: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++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int getMaxRepetitions(std::string s1, int n1,
std::string s2, int n2) {
std::vector firstBlock(s2.size(), -1);
std::vector 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(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(cycles * cycleBlocks);
completed += cycles * cycleCompleted;
}
}
return static_cast(completed / n2);
}
};
代码分析
--------
只在源块边界记录状态,避免把周期切在一个 ``s1`` 块内部;再次到达同一匹配位置时,周期内的完成数量可整体相加,覆盖 ``n1`` 达到百万级的情况。每个状态首次记录一次,之后至多处理剩余周期外的块,时间复杂度为 ``O(|s1| * |s2|)`` 的状态扫描量,额外空间复杂度为 ``O(|s2|)``。