---

0466. 统计重复个数

• 标签：字符串、动态规划
• 难度：困难

题目链接

• 0466. 统计重复个数 - 力扣

题目大意

描述：

定义 $str = [s, n]$ 表示 $str$ 由 $n$ 个字符串 $s$ 连接构成。

• 例如，str == ["abc", 3] == "abcabcabc"。

如果可以从 $s2$ 中删除某些字符使其变为 $s1$，则称字符串 $s1$ 可以从字符串 $s2$ 获得。

• 例如，根据定义，s1 = "abc" 可以从 s2 = "abdbec" 获得，仅需要删除加粗且用斜体标识的字符。

现在给定两个字符串 $s1$ 和 $s2$ 和两个整数 $n1$ 和 $n2$。由此构造得到两个字符串，其中 $str1 = [s1, n1]$、$str2 = [s2, n2]$。

要求：

请你找出一个最大整数 $m$，以满足 $str = [str2, m]$ 可以从 $str1$ 获得。

说明：

• $1 \le s1.length, s2.length \le 10^{3}$。
• $s1$ 和 $s2$ 由小写英文字母组成。
• $1 \le n1, n2 \le 10^{6}$。

示例：

• 示例 1：

输入：s1 = "acb", n1 = 4, s2 = "ab", n2 = 2
输出：2

• 示例 2：

输入：s1 = "acb", n1 = 1, s2 = "acb", n2 = 1
输出：1

解题思路

思路 1：模拟匹配

1. 我们需要找到最大的整数 $m$，使得 $str2$ 重复 $m$ 次后得到的字符串可以从 $str1$ 重复 $n1$ 次后得到的字符串中获得。
2. 由于 $n1$ 和 $n2$ 可能很大（最大 $10^6$），直接构造完整字符串会超出内存限制。
3. 我们可以通过模拟匹配过程来解决：遍历 $str1$ 的每个字符，尝试匹配 $str2$ 的字符。
4. 使用两个指针 $i$ 和 $j$，分别指向 $str1$ 和 $str2$ 的当前位置。
5. 当 $str1[i] = str2[j]$ 时，$j$ 指针前进；否则只前进 $i$ 指针。
6. 当 $j$ 指针到达 $str2$ 末尾时，说明完成了一次 $str2$ 的匹配，计数器加 $1$，$j$ 重置为 $0$。
7. 重复这个过程直到遍历完 $n1$ 个 $str1$，统计总共能匹配多少个完整的 $str2$。
8. 最终答案是 $\lfloor \frac{\text{匹配的 str2 个数}}{n2} \rfloor$。

思路 1：代码

class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        # 统计在 n1 个 s1 中能匹配多少个完整的 s2
        s2_count = 0  # 匹配的 s2 个数
        s2_index = 0  # s2 的当前匹配位置
        
        # 遍历 n1 个 s1
        for i in range(n1):
            # 遍历当前 s1 的每个字符
            for char in s1:
                # 如果当前字符匹配 s2 的当前字符
                if char == s2[s2_index]:
                    s2_index += 1
                    # 如果匹配完一个完整的 s2
                    if s2_index == len(s2):
                        s2_count += 1
                        s2_index = 0  # 重置 s2 的匹配位置
        
        # 返回能构造多少个 [s2, n2]
        return s2_count // n2

思路 1：复杂度分析

• 时间复杂度：$O(n1 \times |s1|)$，其中 $|s1|$ 是字符串 $s1$ 的长度。需要遍历 $n1$ 个 $s1$，每个 $s1$ 需要遍历其所有字符。
• 空间复杂度：$O(1)$，只使用了常数额外空间。