1297. Maximum Number of Occurrences of a Substring

Given a string s, return the maximum number of ocurrences 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 ocurrences 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,让找出符合下列两个条件的任意子串出现的最大次数:1)子串中的不同字符的个数不超过 maxLetters. 2)子串的大小在 minSize 和 maxSize 之间。仔细分析,可以发现这里的 maxSize 其实并没有什么卵用,因为若长度为 maxSize 的子串出现了n次,那么一定有长度为 minSize 的子串至少出现了n次(不信的童鞋可以自己举几个例子看看)。这里其实只要关注长度为 minSize 的子串就行了,用一个 HashMap 来建立子串和其出现次数之间的映射,然后开始遍历原字符串s中的每一个位置,取出长度为 minSize 的子串,然后调用一个子函数 isValid 来检测其不同字符个数是否小于等于 maxLetters,是的话就将其映射值自增1,并且更新结果 res 即可,参见代码如下:

解法一:

class Solution {
public:
    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
        int res = 0, n = s.size();
        unordered_map<string, int> strCnt;
        for (int i = 0; i <= n - minSize; ++i) {
            string cur = s.substr(i, minSize);
            if (isValid(cur, maxLetters)) {
                res = max(res, ++strCnt[cur]);
            }
        }
        return res;
    }
    bool isValid(string cur, int maxLetters) {
        unordered_set<char> st;
        for (char c : cur) st.insert(c);
        return st.size() <= maxLetters;
    }
};

上面的解法基本上是一种暴力搜索法,再来看一种优化后的方法。对于子串中不同字符个数的问题,有一种很常用的方法叫做滑动窗口 Sliding Window,这里维护一个大小为 minSize 的滑动窗口,新建两个 HashMap,一个是建立字符和其出现次数的映射,另一个是建立子串和其出现次数的映射。新建一个变量 start 表示窗口的左边界,初始化为0。遍历原字符串中的每一个字符,在 charCnt 中将其映射值自增1,然后判断若当前窗口长度 i-start+1 大于 minSize,说明该收缩窗口了,将左边界字符的映射值减1,若变成0了,则将该映射移除,然后 start 自增1。若当前窗口长度正好是 minSize,并且 charCnt 中的映射对儿数小于等于 maxLetters,说明找到符合要求的子串了,将其在 strCnt 中映射值自增1,并更新结果 res 即可,参见代码如下:

解法二:

class Solution {
public:
    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
        int res = 0, start = 0, n = s.size();
        unordered_map<char, int> charCnt;
        unordered_map<string, int> strCnt;
        for (int i = 0; i < n; ++i) {
            ++charCnt[s[i]];
            if (i - start + 1 > minSize) {
                if (--charCnt[s[start]] == 0) charCnt.erase(s[start]);
                ++start;
            }
            if (i - start + 1 == minSize && charCnt.size() <= maxLetters) {
                res = max(res, ++strCnt[s.substr(start, i - start + 1)]);
            }
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1297

参考资料:

https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/

https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/discuss/888643/Java-easy-to-understand-solution-O(n)

https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/discuss/457577/C%2B%2B-Greedy-approach-%2B-Sliding-window-O(n).

LeetCode All in One 题目讲解汇总(持续更新中…)

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,快快加入吧~)

知识星球 喜欢请点赞,疼爱请打赏❤️.

微信打赏

|

Venmo 打赏


—|—


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation