X

LEETCODE 1297. Maximum Number of Occurrences of a Substring 解题思路分析

题目大意:

子串的最大出现次数

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1297

解题思路分析:

说实话一开始就没有想到太好的解题思路,尝试了一下暴力解法,居然可以通过,并且效率还不算太低。暴力解即以单词的每一位为开头取出长度为 minSize 到 maxSize 的所有子串,如果子串中的字母种类个数小于等于 maxLetters ,则将该子串加入到map中计数,循环玩所有子串之后,找到map中计数最大的一个即是返回结果。暴力解的时间复杂度为:O(n*26),n为字符串长度。

为了精益求精,接下来我们需要对暴力解进行剪枝优化,优化的关键点在于 minSize 和 maxSize ,比如最小长度为2,最大长度为5时,对于字符串abbbb来说,ab,abb,abbb,abbbb都是合理子串,但我们只要找到第一个(最短的)合理子串即可。因为abbbb包含了ab,如果整个字符串中存在N个abbbb,那么肯定至少包含了N个ab,也就是说,较短的子串个数一定大于等于较长的子串个数。

实现代码:

public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
    // 统计每个子串出现的个数
    Map<String, Integer> map = new HashMap<>();
    int res=0; // 返回结果
    // 以每一个index开头循环
    for(int i=0;i<s.length();i++){
        // 当前子串长度
        int length=0;
        // 当前子串中字母种类个数
        int letterCount=0;
        // 记录出现过的字母
        boolean[] hasLetter = new boolean[26];
        // 当前子串
        StringBuilder sb = new StringBuilder();
        // 循环所有以i开头的子串
        for(int j=i;j<s.length();j++){
            length++; // 子串长度加一
            char c = s.charAt(j); // 当前字符
            sb.append(c); // 当前子串
            // 如果当前字符在当前子串中没有出现过
            if(!hasLetter[c-'a']){
                // 标记为出现过
                hasLetter[c-'a']=true;
                // 字母种类个数加一
                letterCount++;
                // 如果字母种类个数大于maxLetters,退出当前循环
                if(letterCount>maxLetters) break;
            }
            // 当子串长度大于等于minSize时(满足条件的子串)
            if(length>=minSize){
                // 更新当前子串出现的次数
                int count = map.getOrDefault(sb.toString(),0)+1;
                map.put(sb.toString(), count);
                // 更新全局子串出现的最大次数
                res=Math.max(res, count);
                // 找到当前最短子串后,可退出循环。原因参考上文分析
                break;
            }
            // 如果子串长度等于最大长度,退出循环
            if(length==maxSize) break;
        }
    }
    return res;
}

本题解法执行时间为46ms。

Runtime: 46 ms, faster than 83.87% of Java online submissions for Maximum Number of Occurrences of a Substring.

Memory Usage: 40.7 MB, less than 100.00% of Java online submissions for Maximum Number of Occurrences of a Substring.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1297-maximum-number-of-occurrences-of-a-substring-解题思路分析/
Categories: leetcode
kwantong: