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 次，且它们可以重叠。

提示：

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

解题思路

这道题的关键洞察是：如果一个长度为 k 的子串满足条件（不同字符数 ≤ maxLetters），那么它的所有长度为 minSize 的子串也一定满足条件。

基于这个观察，我们可以得出重要结论：只需要考虑长度为 minSize 的子串即可，因为：

  1. 如果存在长度 > minSize 的最优子串，那么它的某个长度为 minSize 的子串出现次数一定不少于它
  2. 较短的子串有更多机会在原字符串中出现

具体算法：

  1. 使用滑动窗口遍历所有长度为 minSize 的子串
  2. 对每个子串，检查其不同字符数是否 ≤ maxLetters
  3. 使用哈希表统计满足条件的子串出现次数
  4. 返回最大出现次数

时间复杂度优化：使用滑动窗口维护字符频次，避免重复计算每个子串的字符统计。

代码实现

class Solution {
public:
    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
        unordered_map<string, int> count;
        unordered_map<char, int> charCount;
        int left = 0;
        int maxFreq = 0;
        
        for (int right = 0; right < s.length(); right++) {
            charCount[s[right]]++;
            
            if (right - left + 1 == minSize) {
                if (charCount.size() <= maxLetters) {
                    string substr = s.substr(left, minSize);
                    count[substr]++;
                    maxFreq = max(maxFreq, count[substr]);
                }
                
                charCount[s[left]]--;
                if (charCount[s[left]] == 0) {
                    charCount.erase(s[left]);
                }
                left++;
            }
        }
        
        return maxFreq;
    }
};

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        from collections import defaultdict, Counter
        
        count = defaultdict(int)
        char_count = Counter()
        left = 0
        max_freq = 0
        
        for right in range(len(s)):
            char_count[s[right]] += 1
            
            if right - left + 1 == minSize:
                if len(char_count) <= maxLetters:
                    substr = s[left:right+1]
                    count[substr] += 1
                    max_freq = max(max_freq, count[substr])
                
                char_count[s[left]] -= 1
                if char_count[s[left]] == 0:
                    del char_count[s[left]]
                left += 1
        
        return max_freq

public class Solution {
    public int MaxFreq(string s, int maxLetters, int minSize, int maxSize) {
        Dictionary<string, int> count = new Dictionary<string, int>();
        Dictionary<char, int> charCount = new Dictionary<char, int>();
        int left = 0;
        int maxFreq = 0;
        
        for (int right = 0; right < s.Length; right++) {
            if (!charCount.ContainsKey(s[right])) {
                charCount[s[right]] = 0;
            }
            charCount[s[right]]++;
            
            if (right - left + 1 == minSize) {
                if (charCount.Count <= maxLetters) {
                    string substr = s.Substring(left, minSize);
                    if (!count.ContainsKey(substr)) {
                        count[substr] = 0;
                    }
                    count[substr]++;
                    maxFreq = Math.Max(maxFreq, count[substr]);
                }
                
                charCount[s[left]]--;
                if (charCount[s[left]] == 0) {
                    charCount.Remove(s[left]);
                }
                left++;
            }
        }
        
        return maxFreq;
    }
}

/**
 * @param {string} s
 * @param {number} maxLetters
 * @param {number} minSize
 * @param {number} maxSize
 * @return {number}
 */
var maxFreq = function(s, maxLetters, minSize, maxSize) {
    const count = new Map();
    let maxOccurrences = 0;
    
    for (let len = minSize; len <= maxSize; len++) {
        for (let i = 0; i <= s.length - len; i++) {
            const substring = s.substring(i, i + len);
            const uniqueChars = new Set(substring).size;
            
            if (uniqueChars <= maxLetters) {
                count.set(substring, (count.get(substring) || 0) + 1);
                maxOccurrences = Math.max(maxOccurrences, count.get(substring));
            }
        }
    }
    
    return maxOccurrences;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × minSize)n 为字符串长度，需要遍历所有长度为 minSize 的子串，每次创建子串需要 O(minSize)
空间复杂度O(n × minSize)哈希表存储子串，最多有 O(n) 个不同子串，每个长度为 minSize

相关题目