题目

给你一个字符串 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 只包含小写英文字母。

思路

全程使用map,最有效的是minSize，如果在长字符串取得了最大值，那么最短字符串出现的次数>=长字符串出现次数

解法

class Solution {
   private boolean checkMaxLetter(String s,int maxLetter){
        Map<Character,Integer> m = new HashMap<>();
        char[] chars=s.toCharArray();
        for(char c:chars){
            m.put(c,m.getOrDefault(c,0)+1);
            if(m.size()>maxLetter) return false;
        }
        return true;
    }
    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        int max = 0;
        Map<String,Integer> m = new HashMap<>();
        for(int i=0;i<=s.length()-minSize;i++){
            String t = s.substring(i,i+minSize);
            m.put(t,m.getOrDefault(t,0)+1);
        }
        for(String t:m.keySet()){
            if(m.get(t)>max&&checkMaxLetter(t,maxLetters)) max = m.get(t);
        }
        return max;
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现