[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