LeetCode 题解工作台
子串的最大出现次数
给你一个字符串 s ，请你返回满足以下条件且出现次数最大的 任意 子串的出现次数： 子串中不同字母的数目必须小于等于 maxLetters 。 子串的长度必须大于等于 minSize 且小于等于 maxSize 。 示例 1： 输入： s = "aababcaab", maxLetters = 2,…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 滑动窗口（状态滚动更新）
答案摘要
根据题目描述，如果一个长串满足条件，那么这个长串的长度为 的子串也一定满足条件。因此，我们只需要枚举 中所有长度为 的子串，然后利用哈希表记录所有子串的出现次数，找出最大的次数作为答案即可。 时间复杂度 $O(n \times m)$，空间复杂度 $O(n \times m)$。其中 和 分别为字符串 的长度以及 的大小。本题中 不超过 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 滑动窗口（状态滚动更新） 题型思路
题目描述
给你一个字符串 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^51 <= maxLetters <= 261 <= minSize <= maxSize <= min(26, s.length)s只包含小写英文字母。
解题思路
方法一：哈希表 + 枚举
根据题目描述，如果一个长串满足条件，那么这个长串的长度为 的子串也一定满足条件。因此，我们只需要枚举 中所有长度为 的子串，然后利用哈希表记录所有子串的出现次数，找出最大的次数作为答案即可。
时间复杂度 ，空间复杂度 。其中 和 分别为字符串 的长度以及 的大小。本题中 不超过 。
class Solution:
def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
ans = 0
cnt = Counter()
for i in range(len(s) - minSize + 1):
t = s[i : i + minSize]
ss = set(t)
if len(ss) <= maxLetters:
cnt[t] += 1
ans = max(ans, cnt[t])
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Understanding of sliding window techniques for substring problems.
- question_mark
Ability to optimize using hash tables and efficiently track occurrences.
- question_mark
Awareness of the trade-offs between time and space complexity for large input sizes.
常见陷阱
外企场景- error
Not correctly handling overlapping substrings or missing edge cases related to character constraints.
- error
Failure to manage space complexity when storing intermediate substrings, especially when `maxSize` is large.
- error
Overcomplicating the solution with unnecessary checks or calculations when simpler, more efficient approaches exist.
进阶变体
外企场景- arrow_right_alt
Adjusting the constraints, such as reducing `maxLetters` or changing `minSize`, to test the robustness of the solution.
- arrow_right_alt
Adapting the solution to handle strings with only one character type (e.g., all 'a's).
- arrow_right_alt
Modifying the problem to count substrings that meet additional conditions, such as having even or odd length.