0466：统计重复个数（★★）

力扣第 466 题

题目

定义 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 <= 106

分析

• 将 [s1,n1] 看作 n1 行，每行都是 s1 的矩阵，便类似 0418
• 按顺序匹配 s2，令 d[k]=i 代表第 i 行最先匹配的是 s2 第 k 个字符
  • 显然 k 的值有限，有限行之后，必然进入循环
  • 用哈希表即可找到第一个循环的开始行 j 和结束行 i
• 遍历时，再用 A[i] 维护前 i 行匹配的 s2 的个数
  • 根据 A[i]、A[j] 即可计算出一个循环匹配的 s2 的个数，从而快速得到结果

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        d,A = {0:0},[0]
        k,s = 0,0
        for i in range(1,n1+1):
            for c in s1:
                if c==s2[k]:
                    s += (k+1)//len(s2)
                    k = (k+1)%len(s2)
            if k in d:
                j = d[k]
                q,r = divmod(n1-j,i-j)
                return (q*(s-A[j])+A[j+r])//n2
            d[k] = i
            A.append(s)
        return s//n2

38 ms