1297. 子串的最大出现次数#

题目描述#

给你一个字符串 s，以及整数 maxLetters、minSize、maxSize。

找出满足以下条件的任意子串的最大出现次数：

子串长度在 [minSize, maxSize] 之间
子串中不同字母的数目不超过 maxLetters

示例 1：

1
输入：s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
2
输出：2

示例 2：

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

解法思路#

核心观察（关键）：如果一个长度为 L > minSize 的子串在 s 中出现了 k 次，那么取它的长度为 minSize 的前缀，该前缀也至少出现 k 次（因为它作为子串的每个出现位置，前缀也随之下标对齐出现）。因此，我们只需要考虑长度为 minSize 的子串，maxSize 本质上不起作用。这就把问题从「不定长」收束成「定长滑窗」。

套用定长滑窗（窗长 minSize）：用长度 26 的计数数组维护窗口内各字母出现次数，用 distinct 维护窗口内不同字母的个数。右端点 s[i] 进窗时更新计数；窗口超过 minSize 时左端点出窗并更新 distinct；一旦窗口长度达到 minSize 且 distinct <= maxLetters，就用哈希表累加该子串的出现次数。

逐步举例（s="aababcaab", maxLetters=2, minSize=3）：

只统计长度为 3 的窗口（不同字母数 ≤ 2）：

窗口（下标）	子串	不同字母数	是否计数
0..2	aab	2	✅
1..3	aba	2	✅
2..4	bab	2	✅
3..5	abc	3	❌
4..6	bca	3	❌
5..7	caa	2	✅
6..8	aab	2	✅

aab 出现 2 次、aba 1 次、bab 1 次、caa 1 次 → 最大出现次数 = 2。✓

复杂度分析#

时间复杂度：O(n)，一次遍历。
空间复杂度：O(n)，哈希表存储不同子串的计数。

代码实现#

1
class Solution:
2
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
3
        cnt = [0] * 26
4
        distinct = 0
5
        freq = {}
6

7
        for i, c in enumerate(s):
8
            idx = ord(c) - 97
9
            if cnt[idx] == 0:
10
                distinct += 1
11
            cnt[idx] += 1
12

13
            if i >= minSize:
14
                idx2 = ord(s[i - minSize]) - 97
15
                cnt[idx2] -= 1
16
                if cnt[idx2] == 0:
17
                    distinct -= 1
18

19
            if i >= minSize - 1 and distinct <= maxLetters:
20
                sub = s[i - minSize + 1:i + 1]
21
                freq[sub] = freq.get(sub, 0) + 1
22

23
        return max(freq.values()) if freq else 0

1
import sys
2
import unittest
3
from pathlib import Path
4

5
sys.path.insert(0, str(Path(__file__).parent))
6
from solution import Solution
7

8

9
class TestMaxFreq(unittest.TestCase):
10
    def setUp(self):
11
        self.solution = Solution()
12

13
    def test_example1(self):
14
        self.assertEqual(self.solution.maxFreq("aababcaab", 2, 3, 4), 2)
15

16
    def test_example2(self):
17
        self.assertEqual(self.solution.maxFreq("aaaa", 1, 3, 3), 2)
18

19
    def test_example3(self):
20
        self.assertEqual(self.solution.maxFreq("aabcabcab", 2, 2, 3), 3)
21

22
    def test_no_valid_substring(self):
23
        self.assertEqual(self.solution.maxFreq("abcde", 1, 2, 3), 0)
24

25
    def test_max_letters_zero(self):
26
        self.assertEqual(self.solution.maxFreq("abc", 0, 1, 1), 0)
27

28

29
if __name__ == "__main__":
30
    unittest.main()