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.

Solution:

Approach 1:

class Solution {
    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) 
    {
        if(s == null || s.length() == 0 || maxLetters == 0) return 0;
        HashMap<String, Integer> hm = new HashMap<>();
        int max = 0;
        for(int i = 0; i < s.length() - minSize + 1; i++) {
            String cur = s.substring(i, i + minSize);
            if(isValid(cur, maxLetters,maxSize)) {
                hm.put(cur, hm.getOrDefault(cur, 0) + 1);
                max = Math.max(max, hm.get(cur));
            }
        }
        return max;
    }
	
    boolean isValid(String cur, int maxLetters,int maxsize) 
    {
        HashSet<Character> hs = new HashSet<>();
        for(char c: cur.toCharArray()) hs.add(c);
        return hs.size() <= maxLetters && cur.length()<=maxsize;
    }
}

Approach 2:

class Solution {
    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        int[] ch = new int[26];
        int Letters=0,NoOfOccurrence=0;
        Map<String,Integer> map = new HashMap<>();
        for(int i=0,j=0;i<s.length();i++) {
            char c = s.charAt(i);
            if(++ch[c-'a']==1) {
                Letters++;
            }
            while(Letters>maxLetters || i-j+1>maxSize) {
                if(--ch[s.charAt(j)-'a']==0) Letters--;
                j++;
            }
            while(i-j+1>=minSize) {
                String s1=s.substring(j,i+1);
                map.put(s1,map.getOrDefault(s1,0)+1);
                NoOfOccurrence=Math.max(NoOfOccurrence,map.get(s1));
                if(--ch[s.charAt(j)-'a']==0) Letters--;
                j++;
            }
        }
        return NoOfOccurrence;
    }
}