子串的最大出现次数

标签: 哈希表 字符串 滑动窗口

难度: Medium

给你一个字符串 s ，请你返回满足以下条件且出现次数最大的 任意 子串的出现次数：

  • 子串中不同字母的数目必须小于等于 maxLetters 。
  • 子串的长度必须大于等于 minSize 且小于等于 maxSize 。

示例 1：

输入：s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
输出：2
解释：子串 "aab" 在原字符串中出现了 2 次。
它满足所有的要求：2 个不同的字母，长度为 3 （在 minSize 和 maxSize 范围内）。

示例 2：

输入：s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
输出：2
解释：子串 "aaa" 在原字符串中出现了 2 次，且它们有重叠部分。

示例 3：

输入：s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3
输出：3

示例 4：

输入：s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
输出：0

提示：

  • 1 <= s.length <= 10^5
  • 1 <= maxLetters <= 26
  • 1 <= minSize <= maxSize <= min(26, s.length)
  • s 只包含小写英文字母。

Submission

运行时间: 95 ms

内存: 0.0 MB

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        # only include the min size array cases
        count = collections.Counter(s[i:i + minSize] for i in range(len(s) - minSize + 1))
        return max([count[w] for w in count if len(set(w)) <= maxLetters] + [0])

       
    # def getMaxFreq(self, s: str, maxLetters: int, crr_size: int):

Explain

题解的核心思路是先考虑最小子串长度 `minSize`，因为较小的子串更可能在字符串中重复出现。首先，使用一个滑动窗口的方法生成所有长度为 `minSize` 的子串，并利用 `collections.Counter` 统计这些子串的出现频率。随后，遍历这个频率字典，选出那些满足“子串中不同字母的数目不超过 `maxLetters`”的子串，并记录它们的最大出现次数。这种方法避免了考虑 `maxSize`，因为更长的子串出现次数通常不会超过最小长度子串的出现次数。

时间复杂度: O(n * minSize)

空间复杂度: O(n)

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        # 使用Counter统计所有长度为minSize的子串的出现次数
        count = collections.Counter(s[i:i + minSize] for i in range(len(s) - minSize + 1))
        # 计算满足最大不同字母数要求的子串的最大频率，如果没有则为0
        return max([count[w] for w in count if len(set(w)) <= maxLetters] + [0])

Explore

在处理子串的最大出现次数时，选择 `minSize` 的原因是基于统计的观察，即更短的子串更有可能在字符串中频繁出现。由于任何长度大于 `minSize` 且小于或等于 `maxSize` 的子串包含了长度为 `minSize` 的子串，如果 `minSize` 子串的出现频率已不高，其包含的更长子串的出现频率自然也不会更高。因此，直接分析 `minSize` 长度的子串足以找到可能的最大频率，无需额外计算更长子串的频率，从而提高算法的效率。

是的，使用 `collections.Counter` 统计子串时，考虑了字符串中的重叠子串。这意味着每一个可能的子串位置都被生成并计数，包括那些起始索引相邻的重叠子串。这种方法确保了所有可能的子串都被计算在内，从而可以准确地找到出现频率最高的子串。对结果的影响是使得计算更全面，但也意味着计算量增大，尤其是在字符串较长时。

这样做是为了确保只考虑那些符合“子串中不同字母的数量不超过 `maxLetters`”的条件的子串。直接从计数器中获取最大值可能包括了不符合字母数量条件的子串，导致结果不正确。通过添加 `[0]`，还能处理所有子串都不符合条件时的情况，此时函数可以安全返回 `0` 作为结果，避免在空列表上调用 `max` 函数导致错误。

当 `minSize` 接近于字符串 `s` 的长度时，滑动窗口的生成子串的操作变得较少，因为可以生成的子串数量减少（接近于 `len(s) - minSize + 1`）。在这种情况下，算法的效率相对较高，因为处理的数据量减少了。然而，如果 `minSize` 等于 `s` 的长度，那么只需要考虑整个字符串作为子串的情况，这可以进一步简化为直接计算字符串是否满足 `maxLetters` 条件并返回1或0。