Leetcode_1297_Maximum Number of Occurrences of a Substring

[lihe]

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.

Example 3:

Input: s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3
Output: 3

Example 4:

Input: s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
Output: 0

Constraints:

• 1 <= s.length <= 10^5
• 1 <= maxLetters <= 26
• 1 <= minSize <= maxSize <= min(26, s.length)
• s only contains lowercase English letters.

class Solution {
    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        char[] chars = s.toCharArray();
        Map<String, Integer> map = new HashMap<>();
        for(int i = 0; i <= chars.length - minSize; i++){
            if(counter(chars, i, i + minSize - 1) <= maxLetters){
                String key = String.valueOf(chars, i, minSize);
                map.put(key, map.getOrDefault(key, 0) + 1);
            }
        }
        int max = 0;
        for(Integer x: map.values()){
            max = Math.max(max, x);
        }
        return max;
    }
    
    private int counter(char[] chars, int start, int end){
        Set<Character> set = new HashSet<>();
        for(int i = start; i <= end; i++){
            set.add(chars[i]);
        }
        return set.size();
    }
}