点击上方蓝字设为星标LeetCode 题解 | 1297.子串的最大出现次数

下面开始今天的学习~

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;
}

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

原文始发于微信公众号(五分钟学算法):LeetCode 题解 | 1297.子串的最大出现次数