[LeetCode] 1297. Maximum Number of Occurrences of a Substring

Given a string s, return the maximum number of occurrences of any substring under the following rules:
The number of unique characters in the substring must be less than or equal to maxLetters.
The substring size must be between minSize and maxSize inclusive.

Example 1:
Input: s = “aababcaab”, maxLetters = 2, minSize = 3, maxSize = 4
Output: 2
Explanation: Substring “aab” has 2 occurrences in the original string.
It satisfies the conditions, 2 unique letters and size 3 (between minSize and maxSize).

Example 2:
Input: s = “aaaa”, maxLetters = 1, minSize = 3, maxSize = 3
Output: 2
Explanation: Substring “aaa” occur 2 times in the string. It can overlap.

Constraints:
1 <= s.length <= 105
1 <= maxLetters <= 26
1 <= minSize <= maxSize <= min(26, s.length)
s consists of only lowercase English letters.

子串的最大出现次数。

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

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

思路

思路是固定长度的滑动窗口。

这道题的难点在于需要明白题目的意思，如果完全明白题意，则题目会很简单。题目要我们找一个子串，满足两个条件：

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

第一个条件很好理解，如果我们能确定一个子串，那我们用 hashset 去看这个子串里有几个不同字母即可。

第二个条件很好理解但是不好判断，因为他需要子串长度介于 [minSize, maxSize] 之间。但是如果 minSize 和 maxSize 差距过大，找子串的工作的时间复杂度就会很高。但是这里仔细想想，因为找的是子串，那么如果你能找到一个出现次数为 X 的子串 A，那么 A 中的任意一个子串的出现次数也是 X。所以这里其实我们找的是一个长度为 minSize 的子串。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        int n = s.length();
        int k = minSize;
        HashMap<String, Integer> map = new HashMap<>();
        String first = s.substring(0, k);
        int res = 0;
        if (helper(first, maxLetters)) {
            map.put(first, 1);
            res = 1;
        }
        for (int i = 1; i + k <= n; i++) {
            String str = s.substring(i, i + k);
            if (helper(str, maxLetters)) {
                map.put(str, map.getOrDefault(str, 0) + 1);
                res = Math.max(res, map.get(str));
            }
        }
        return res;
    }

    private boolean helper(String s, int maxLetters) {
        Set<Character> set = new HashSet<>();
        for (char c : s.toCharArray()) {
            set.add(c);
        }
        return set.size() <= maxLetters;
    }
}