Leetcode: 【每日一题】- 2020-01-08 - 1297. 子串的最大出现次数

[azl397985856]

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-number-of-occurrences-of-a-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[unclegem]

Java题解 简单明了

注意题目细节中的maxSize范围，那么就可以发现暴力解法可以做。

其实可以用滑动窗口来做，窗口大小为minSize即可。理由大致如下：

• 一个大于minSize长度的字串若是满足条件，那么该字串其中必定有至少一个长度为minSize的字串满足条件。
• 因此一个大于minSize长度的字串出现了T次，那么该字串其中必定有一个长度为minSize的字串出现了T次。

    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {

        Map<String, Integer> counter = new HashMap<>();
        int res = 0;
        for (int i = 0; i < s.length() - minSize + 1; i++) {

            String substr = s.substring(i, i + minSize);
            if (checkNum(substr, maxLetters)) {

                int newVal = counter.getOrDefault(substr, 0) + 1;
                counter.put(substr, newVal);
                res = Math.max(res, newVal);
            }
        }

        return res;
    }

    public boolean checkNum(String substr, int maxLetters) {

        Set<Character> set = new HashSet<>();
        for (int i = 0; i < substr.length(); i++)
            set.add(substr.charAt(i));

        return set.size() <= maxLetters;
    }

[azl397985856]

@unclegem 一看就知道高手， 看条件看的这么犀利 做了不少题吧？

[unclegem]

@unclegem 一看就知道高手， 看条件看的这么犀利 做了不少题吧？

😂还好，就是有的题范围卡的松，一般第一种解法就上bf试试了。

[azl397985856]

@unclegem Similar Solution with Python3， But TLE：

# https://leetcode-cn.com/problems/maximum-number-of-occurrences-of-a-substring/
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        n = len(s)
        letters = set()
        cnts = dict()
        res = 0
        for i in range(n - minSize + 1):
            length = minSize
            while i + length <= n and length <= maxSize:
                t = s[i:i + length]
                for c in t:
                    if len(letters) > maxLetters:
                        break
                    letters.add(c)
                if len(letters) <= maxLetters:
                    cnts[t] = cnts.get(t, 0) + 1
                    res = max(res, cnts[t])
                letters.clear()
                length += 1
        return res

[unclegem]

@unclegem Similar Solution with Python3， But TLE：

# https://leetcode-cn.com/problems/maximum-number-of-occurrences-of-a-substring/
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        n = len(s)
        letters = set()
        cnts = dict()
        res = 0
        for i in range(n - minSize + 1):
            length = minSize
            while i + length <= n and length <= maxSize:
                t = s[i:i + length]
                for c in t:
                    if len(letters) > maxLetters:
                        break
                    letters.add(c)
                if len(letters) <= maxLetters:
                    cnts[t] = cnts.get(t, 0) + 1
                    res = max(res, cnts[t])
                letters.clear()
                length += 1
        return res

你这个窗口大小没固定的吧，固定为minSize应该不会超时。

[azl397985856]

@unclegem wow

[unclegem]

@unclegem wow

这样不会TLE了

    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:

        counter, res = {}, 0
        for i in range(0, len(s) - minSize + 1):

            sub = s[i : i + minSize]
            if len(set(sub)) <= maxLetters:

                counter[sub] = counter.get(sub, 0) + 1
                res = max(res, counter[sub])

        return res;

[azl397985856]

@unclegem big thanks for u ❤️

# https://leetcode-cn.com/problems/maximum-number-of-occurrences-of-a-substring/
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        n = len(s)
        letters = set()
        cnts = dict()
        res = 0
        for i in range(n - minSize + 1):
            t = s[i:i + minSize]
            for c in t:
                if len(letters) > maxLetters:
                    break
                letters.add(c)
            if len(letters) <= maxLetters:
                cnts[t] = cnts.get(t, 0) + 1
                res = max(res, cnts[t])
            letters.clear()
        return res

[azl397985856]

@unclegem wow

这样不会TLE了

    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:

        counter, res = {}, 0
        for i in range(0, len(s) - minSize + 1):

            sub = s[i : i + minSize]
            if len(set(sub)) <= maxLetters:

                counter[sub] = counter.get(sub, 0) + 1
                res = max(res, counter[sub])

        return res;

TQL

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[azl397985856]

补充： 这道题的 maxSize 是无用信息， 并不需要用到。