Maximum Number of occurrences of Substring

Problem Statement:

Given a string s, return the maximum number of occurrences of anysubstring 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 maxSizeinclusive.

Example 1:

Input: s = “aababcaab”, maxLetters = 2, minSize = 3, maxSize = 4 Output: 2 Explanation: Substring “aab” has 2 occurrences in the original string but “aba” has only 1 occurence (there maybe more such strings). They satisfies the conditions, 2 unique letters and size 3 (between minSize and maxSize) but “aab” has max occurrence.

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.

Solution:

class Solution {
    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        int maxOccurrence = 0;
        int start = 0;
        int end = 0;
        int size = s.length();
        int uniqueChar = 0;
        HashMap<Character, Integer> charFMap = new HashMap<>();
        HashMap<String, Integer> stringFMap = new HashMap<>();
 
        // Sliding window approach
        while (end < size) {
            Character ch = s.charAt(end);
            
            // Update the frequency of the character in the charFMap
            charFMap.put(ch, charFMap.getOrDefault(ch, 0) + 1);
            
            // Check if the current window size is within the valid range
            if (end - start + 1 >= minSize && end - start + 1 <= maxSize) {
                // Check if the number of unique characters in the current window is within the limit
                if (charFMap.size() <= maxLetters) {
                    // Extract the substring from start to end (inclusive)
                    String substr = s.substring(start, end + 1);
                    
                    // Update the frequency of the substring in the stringFMap
                    stringFMap.put(substr, stringFMap.getOrDefault(substr, 0) + 1);
                }
                
                // Shrink the window by moving the start pointer
                charFMap.put(s.charAt(start), charFMap.get(s.charAt(start)) - 1);
                
                // Remove the character from charFMap if its frequency becomes 0
                charFMap.remove(s.charAt(start), 0);
                start++;
            }
            end++;
        }
 
        for(Integer freq: stringFMap.values()){
            maxOccurrence = Math.max(maxOccurrence, freq);
        }
 
        return maxOccurrence;
    }
}