LeetCode 题解 | 1297.子串的最大出现次数

逃离我推掉我的手 2023-06-30 04:21 16阅读 0赞

点击上方蓝字设为星标![format_png][]

下面开始今天的学习～

![format_png 1][]

今天分享的题目来源于 LeetCode 第 1297 题：子串的最大出现次数。

### 题目描述 ###

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

### 题目解析 ###

给定一个字符串，找出出现次数最多的子串，但是有两个限制条件：

*  子串里面的不同的字符的个数不能超过 maxLetters
 *  子串的长度必须在 minSize 和 maxSize 之间

这道题目，最初的想法就是使用 **滑动窗口**，但是这里有个问题，子串的长度既有上限也有下限，如果同时带着这两个限制条件去做滑动窗口，你会发现我们其实行不通。

举个例子，假如 `minSize` 是 3，`maxSize` 是 6，如果当前滑动窗口的大小是 4，而且子串里面不同字符的个数也不超过 maxLtters，也就是说两个限制条件均满足。

那么你是考虑移动左指针还是右指针？

仔细去想，如果按这种思路，其实窗口的两头并没有严格的限制条件去控制。

现在我们可以思考这样一个问题，**是不是我们必须考虑 minSize 和 maxSize，还是说只用考虑其中一个？** 这道题目有一个很巧妙的地方在于，我们只需要考虑 `minSize` 即可，举个例子：

s = "aabcaabcaab", maxLetters = 2, minSize = 2, maxSize = 3
    
    aab 出现次数最多，且满足限制条件
    只要 aab 满足限制条件，它的子串 ab 也必定满足限制条件，且出现次数必定不低于 aab

### 参考代码 ###

public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        Map<String, Integer> counts = new HashMap<>();
    
        int n = s.length();
        char[] sArr = s.toCharArray();
        int[] hash = new int[26];
    
        int l = 0, result = 0, unique = 0;
        for (int r = 0; r < n; ++r) {
            if (hash[sArr[r] - 'a']++ == 0) {
                unique++;
            }
    
            // 如果条件不满足，移动左指针，缩小窗口，使条件满足
            while (unique > maxLetters || r - l + 1 > minSize) {
                if (hash[sArr[l++] - 'a']-- == 1) {
                    unique--;
                }
            }
    
            // 条件满足，更新答案，这里只考虑 minSize
            if (r - l + 1 == minSize) {
                String cur = s.substring(l, r + 1);
                counts.put(cur, counts.getOrDefault(cur, 0) + 1);
                result = Math.max(result, counts.get(cur));
            }
        }
    
        return result;
    }

![format_png 2][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9pY0hvZXJLTzNOakxHa0wzSmljWnh6WlVsTVBXYU9FVXRpYVZ5RHQ1QU9hSUpOa0xhbHRYT1lSaWFHU2J5aWJneFFzVkxSYXo5SnhmTjZLVkJtU05GYkZlNkx3LzY0MA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9taWFabTA1NHZVaWJ1Mlo1T0d1SXpidXdUaWFpYmlhNWxNU3pJM29iS1B4SDlLeGtTeTdQM3NkNjlpY0dUR3kxVGVXUXIzTjIxUVNjcnJpYmFIRGJYRmJrd1lnOXcvNjQw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVEzMENBYUxzOVhEMEpwQXNxYm1HbDNjM0VTVEE5MGg0TnpIbHhVZXV4aWM3bUdyS2xTTlV1S25SYWFTNVpiRHg1d0RxaWNpY1VhcFVBQ0EvNjQw?x-oss-process=image/format,png