统计重复个数

标签: 字符串 动态规划

难度: Hard

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

Submission

运行时间: 27 ms

内存: 16.2 MB

class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        cnt1, cnt2, idx = 0, 0, 0
        mp = dict()
        while True:
            cnt1 += 1
            for ch in s1:
                if ch == s2[idx]:
                    idx += 1
                    if idx == len(s2):
                        cnt2 += 1
                        idx = 0
            if cnt1 == n1:
                return cnt2 // n2 
            if idx not in mp:
                mp[idx] = (cnt1, cnt2)
            else:
                precnt1, precnt2 = mp[idx]
                ans = precnt2 + (n1 - precnt1) // (cnt1 - precnt1) * (cnt2 - precnt2)
                t = (n1 - precnt1) % (cnt1 - precnt1)
                for i in range(t):
                    for ch in s1:
                        if ch == s2[idx]:
                            idx += 1
                            if idx == len(s2):
                                ans += 1
                                idx = 0
                return ans // n2

Explain

这个题解使用哈希表来记录在 s1 的每个完整循环中，s2 完整出现的次数以及当前匹配到的 s2 的下标。当再次出现相同的 s2 下标时，说明出现了循环节，可以直接计算出在剩余的 s1 循环中，s2 完整出现的次数，从而避免了后续的循环计算。最后将 s2 出现的总次数除以 n2，得到 s2 在 s1 中重复出现的最大次数。

时间复杂度: O(mn)

空间复杂度: O(n)

class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        cnt1, cnt2, idx = 0, 0, 0
        mp = dict()
        while True:
            cnt1 += 1  # 当前 s1 的循环次数
            for ch in s1:
                if ch == s2[idx]:  # 如果当前字符匹配
                    idx += 1  # 移动 s2 的下标
                    if idx == len(s2):  # 如果 s2 完全匹配
                        cnt2 += 1  # s2 出现次数加 1
                        idx = 0  # s2 下标重置为 0
            if cnt1 == n1:  # 如果 s1 已经循环了 n1 次
                return cnt2 // n2  # 返回 s2 出现的总次数除以 n2
            if idx not in mp:  # 如果当前 s2 下标没有出现过
                mp[idx] = (cnt1, cnt2)  # 记录当前 s1 的循环次数和 s2 的出现次数
            else:  # 如果当前 s2 下标出现过，说明出现了循环节
                precnt1, precnt2 = mp[idx]  # 取出上一次出现该下标时的 s1 循环次数和 s2 出现次数
                # 计算循环节中 s2 出现的次数
                ans = precnt2 + (n1 - precnt1) // (cnt1 - precnt1) * (cnt2 - precnt2)
                t = (n1 - precnt1) % (cnt1 - precnt1)  # 计算剩余的不足一个循环节的部分
                for i in range(t):  # 遍历剩余的部分
                    for ch in s1:
                        if ch == s2[idx]:
                            idx += 1
                            if idx == len(s2):
                                ans += 1
                                idx = 0
                return ans // n2  # 返回 s2 出现的总次数除以 n2

Explore

使用哈希表可以快速检测到s2的某个下标是否在之前的s1循环中已经出现过，并记录下该下标第一次出现时s1的循环次数和s2的出现次数。这样做的目的是为了发现循环节，即一种模式的重复，这种重复可以让我们通过简单的算术运算直接计算出剩余循环中s2的出现次数，而不需要继续逐个匹配s1和s2，从而大大提高算法的效率。

当我们在哈希表中发现一个已经存在的s2的下标时，这表示从上一次该下标出现到当前位置，s1和s2之间的匹配形成了一个循环节。这意味着在这个循环节内s1和s2的匹配模式会重复出现。通过记录循环开始和结束时的s1循环次数和s2出现次数，我们可以计算出一个完整循环节中s2出现的次数，并用它来估算总的循环次数内s2的出现次数。这种方法的正确性基于循环节的重复性，即每个循环节s2出现的次数是固定的。

当s2的某个下标在哈希表中已经存在时，我们首先提取出这个下标首次出现时和当前的s1循环次数和s2出现次数。这两个点标记了循环节的起始和终止。我们可以通过这两个点计算一个完整循环节中s1和s2的匹配次数。接着，我们可以根据已经完成的s1循环次数和总需求的s1循环次数，来估算还需要多少完整的循环节，以及最后剩余不完整循环节的s1和s2匹配次数。这样就可以计算出总的s2出现次数。

这些信息帮助我们确定了s2的某个下标在s1的多次循环中首次和再次出现的位置。通过比较这两个点的s1循环次数和s2出现次数，我们可以识别出循环节的长度和模式。一旦确定了循环节，我们就可以使用这个信息来预测未来的匹配模式，而不需要继续进行逐字符的匹配。这大大提高了算法处理大数据量时的效率和性能。