What is the core pattern used in Count The Repetitions?

The problem relies on state transition dynamic programming, tracking the matching position in s2 through repeated s1 iterations.

How do cycles improve performance in this problem?

Detecting repeating states allows us to skip redundant iterations and multiply counts, avoiding timeouts for large n1.

Can we use a brute-force approach for small inputs?

Yes, iterating over all characters works for small n1 and n2, but it fails for the upper constraint limits.

What common mistakes lead to wrong answers?

Not resetting the s2 pointer correctly per s1 repetition or ignoring overlapping cycles causes miscounting.

Why does dynamic programming fit Count The Repetitions?

DP efficiently tracks progress across repeated sequences and handles state transitions, which is essential for counting subsequences in repeated strings.

#466

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

统计重复个数

定义 str = [s, n] 表示 str 由 n 个字符串 s 连接构成。例如， str == ["abc", 3] =="abcabcabc" 。如果可以从 s2 中删除某些字符使其变为 s1 ，则称字符串 s1 可以从字符串 s2 获得。例如，根据定义， s1 = "abc" 可以从 …

字符串动态规划

题目描述

定义 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：

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

示例 2：

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

提示：

1 <= s1.length, s2.length <= 100
s1 和 s2 由小写英文字母组成
1 <= n1, n2 <= 10⁶

lightbulb

解题思路

方法一：预处理 + 递推

我们预处理出以字符串 $s_2$ 的每个位置 $i$ 开始匹配一个完整的 $s_1$ 后，下一个位置 $j$ 以及经过了多少个 $s_2$ ，即 $d[i] = (cnt, j)$ ，其中 $cnt$ 表示匹配了多少个 $s_2$ ，而 $j$ 表示字符串 $s_2$ 的下一个位置。

接下来，我们初始化 $j=0$ ，然后循环 $n1$ 次，每一次将 $d[j][0]$ 加到答案中，然后更新 $j=d[j][1]$ 。

最后得到的答案就是 $n1$ 个 $s_1$ 所能匹配的 $s_2$ 的个数，除以 $n2$ 即可得到答案。

时间复杂度 $O(m \times n + n_1)$ ，空间复杂度 $O(n)$ 。其中 $m$ 和 $n$ 分别是 $s_1$ 和 $s_2$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        n = len(s2)
        d = {}
        for i in range(n):
            cnt = 0
            j = i
            for c in s1:
                if c == s2[j]:
                    j += 1
                if j == n:
                    cnt += 1
                    j = 0
            d[i] = (cnt, j)

        ans = 0
        j = 0
        for _ in range(n1):
            cnt, j = d[j]
            ans += cnt
        return ans // n2

speed

复杂度分析

指标	值
时间	complexity is O(\|s1\| + \|s2\|) in practice due to cycle optimization, instead of naive O(n1\|s1\|\|s2\|). Space complexity is O(\|s2\|) for storing states to detect cycles.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect you to recognize subsequence patterns within repeated strings.
question_mark
Look for cycle detection to optimize repeated sequence counting.
question_mark
Consider how state transitions map the matching progress of s2 inside s1.

warning

常见陷阱

外企场景

error
Attempting naive iteration over str1 fully will time out due to large n1.
error
Ignoring cycles or repeated states leads to unnecessary computation.
error
Misaligning the subsequence pointer resets after each s1 repetition.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute the maximum number of s2 occurrences in str1 when n1 is extremely large and cannot be fully materialized.
arrow_right_alt
Modify the problem to return the positions in str1 where each s2 repetition ends.
arrow_right_alt
Change s2 to allow optional characters, increasing the dynamic programming state complexity.

help

常见问题

外企场景

继续练习

#467 环绕字符串中唯一的子字符串 #472 连接词 #474 一和零