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

点击上方蓝字设为星标

今天分享的题目来源于 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;
}