Maximum Number of Occurrences of a Substring || Beats 100% ☑️ || Optimized Trie + Sliding Window 🚀
IntuitionThe problem requires finding the most frequently occurring substring of at least minSize and at most maxSize, with at most maxLetters distinct characte
# Intuition
The problem requires finding the most frequently occurring substring of at least minSize and at most maxSize, with at most maxLetters distinct characters.
•	Instead of generating all substrings explicitly, we maintain a sliding window of minSize and track substrings dynamically.
•	A Trie (Prefix Tree) efficiently stores substrings while counting occurrences.
•	We also use a character frequency array to efficiently track distinct characters.

# Approach
1.	Initialize Character Frequency Array:
	•	Use an array charCount[26] to track character occurrences.
	•	Maintain a distinctCount variable to count distinct characters in the window.
2.	Sliding Window (First minSize Substring):
	•	Populate charCount for the first minSize characters.
	•	If it meets the maxLetters condition, insert it into the Trie and update max frequency.
3.	Slide the Window Across s:
	•	Remove the leftmost character from the window and update distinctCount.
	•	Add the new character and update distinctCount.
	•	If distinctCount ≤ maxLetters, insert the substring into the Trie and update the max frequency.
4.	Trie Insertion & Frequency Count:
	•	Insert the substring into the Trie.
	•	Update the frequency count of the node representing that substring.
5.	Return the Maximum Frequency Found.

# Complexity
- Time complexity:
	•	Time Complexity:  O(N) 
	•	Each character is processed once in the sliding window  O(N) .
	•	Trie insertions take  O(\text{minSize}) , but they are limited to  O(N)  overall.
	•	Overall, the approach runs in linear time.

- Space complexity:
    •	The Trie stores at most  O(N)  substrings.
	•	The character frequency array uses  O(26) = O(1)  space.
	•	Overall, this is an optimal memory-efficient solution.

# Code
```java []
import java.util.HashMap;

class Solution {
    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        char[] chrs = s.toCharArray();
        if (minSize > chrs.length)
            return 0;

        int res = 0;
        TrieNode root = new TrieNode();
        int[] charCount = new int[26]; // Character frequency array
        int distinctCount = 0;

        for (int i = 0; i < minSize; i++) {
            int idx = chrs[i] - 'a';
            if (charCount[idx]++ == 0) {
                distinctCount++;
            }
        }

        if (distinctCount <= maxLetters) {
            res = Math.max(insertTrie(root, chrs, 0, minSize), res);
        }

        for (int i = minSize; i < chrs.length; i++) {
            int removeIdx = chrs[i - minSize] - 'a';
            if (--charCount[removeIdx] == 0) {
                distinctCount--;
            }

            int addIdx = chrs[i] - 'a';
            if (charCount[addIdx]++ == 0) {
                distinctCount++;
            }

            if (distinctCount <= maxLetters) {
                res = Math.max(insertTrie(root, chrs, i - minSize + 1, minSize), res);
            }
        }

        return res;
    }

    private int insertTrie(TrieNode root, char[] chrs, int start, int minSize) {
        TrieNode node = root;
        for (int i = start; i < start + minSize; i++) {
            int idx = chrs[i] - 'a';
            if (node.next[idx] == null)
                node.next[idx] = new TrieNode();
            node = node.next[idx];
        }
        node.count++;
        return node.count;
    }
}

class TrieNode {
    TrieNode[] next = new TrieNode[26];
    int count = 0;
}
```
['Java']