[leetcode/lintcode 题解] 算法面试真题详解:最频繁出现的子串-阿里云开发者社区

开发者社区> 算法编程> 正文
登录阅读全文

[leetcode/lintcode 题解] 算法面试真题详解:最频繁出现的子串

简介: [leetcode/lintcode 题解] 算法面试真题详解:最频繁出现的子串

描述
给定一个字符串,我们想知道满足以下两个条件的子串最多出现了多少次:

  1. 子串的长度在minLength,maxLength之间
  2. 子串的字符种类不超过maxUniquemaxUnique

写一个函数 getMaxOccurrences ,其返回满足条件的子串最多出现次数。

  • 2≤n≤1052≤n≤105
  • 2≤minLength≤maxLength≤262≤minLength≤maxLength≤26
  • maxLength<nmaxLength<n
  • 2≤maxUnique≤262≤maxUnique≤26
  • ss仅包含小写字母

在线评测地址:领扣题库官网

样例1
输入: 
s = "abcde"
minLength = 2
maxLength = 5
maxUnique = 3
输出: 
1
解释:
符合条件的子串有 ab, bc, cd, de, abc, bcd, cde 。每一个子串只出现了一次,因此答案是1。

解题思路
我们可以使用滑动窗口的做法。显然,题目中的maxLengthmaxLength是没有用的,因此我们只需要以枚举所有minLengthminLength长的子串,判断其是否符合maxUniquemaxUnique的条件。如果符合,进行计数即可。
源代码

public class Solution {
    /**
     * @param s: string s
     * @param minLength: min length for the substring
     * @param maxLength: max length for the substring
     * @param maxUnique: max unique letter allowed in the substring
     * @return: the max occurrences of substring
     */
    public int getMaxOccurrences(String s, int minLength, int maxLength, int maxUnique) {
        // write your code here
        int[] letterCount = new int[26];  /*count letter*/ 
        char[] strs = s.toCharArray();
        Map<String,Integer> stringCount = new HashMap<>();  /*count specific string satisfy requirement.*/
        int start = 0, end = start + minLength - 1, letterTotal = 0, ans = 0; /*letterTotal stores current total number of distinct letter. */
                /*deal with the first string with minLength. */
        for(int i = start; i <= end; i++){
            if(letterCount[strs[i] - 'a'] == 0) letterTotal++;
            letterCount[strs[i] - 'a']++;
        }
        if(letterTotal <= maxUnique){
            stringCount.put(s.substring(start, end + 1), 1);
            ans = 1;
        }
                
                /*slide in one letter, slide out one letter, and check if the substring in the sliding window satisfy the requirement. */
                
        end++;
        while(end < s.length()){
            if(letterCount[strs[end] - 'a']++ == 0) letterTotal++;
            if(letterCount[strs[start] - 'a']-- == 1) letterTotal--;
            start++;
            if(letterTotal <= maxUnique){
                String curStr = s.substring(start, end + 1);
                stringCount.put(curStr, stringCount.getOrDefault(curStr, 0) + 1);
                ans = Math.max(ans, stringCount.get(curStr));
            }
            end++;
        }
        return ans;
    }
}

更多题解参考:九章官网solution

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: