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

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

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

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

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

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

样例1
s = "abcde"
minLength = 2
maxLength = 5
maxUnique = 3
符合条件的子串有 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

本文转自网络，原文链接：https://developer.aliyun.com/article/783991
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！