# Maximum Number of Occurrences of a Substring
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-occurrences-of-a-substring
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Hash Table, String
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Hubspot](https://scaleengineer.com/companies/hubspot), [Roblox](https://scaleengineer.com/companies/roblox)
---
## Problem
Given a string `s`, return the maximum number of occurrences 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 occurrences 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.

**Constraints:**

* `1 <= s.length <= 105`
* `1 <= maxLetters <= 26`
* `1 <= minSize <= maxSize <= min(26, s.length)`
* `s` consists of only lowercase English letters.

# Approaches
## Brute-Force with All Substring Lengths
This approach iterates through all possible substring lengths from `minSize` to `maxSize`. For each length, it generates all substrings, checks if they are valid (i.e., have at most `maxLetters` unique characters), and counts their occurrences using a HashMap.
**Time:** O((maxSize - minSize) * N * L), where `L` is the substring length. The nested loops run `(maxSize - minSize) * N` times. Inside, substring creation and unique character counting each take `O(L)`. This is very inefficient. · **Space:** O(K * L), where `K` is the number of unique valid substrings and `L` is their average length. In the worst case, this can be `O(N * L)`.
**Pros:** Simple to understand and implement as it's a direct interpretation of the problem statement.
**Cons:** Highly inefficient due to redundant computations and checking unnecessary substring lengths.; Likely to result in a 'Time Limit Exceeded' error on larger inputs.
### Explanation
This approach directly translates the problem statement into code without any optimization. It considers every possible substring that fits the length criteria (`minSize` to `maxSize`).

It uses nested loops. The outer loop iterates through all possible substring lengths from `minSize` to `maxSize`. The inner loop iterates through the string `s` to generate all substrings of the current length.

For each generated substring, a helper function is called to count its unique characters. If this count is within the `maxLetters` limit, the substring is considered valid.

A `HashMap` is used to store each unique valid substring and its frequency. After checking all possible substrings, the maximum frequency stored in the map is returned.

The main drawback is its performance. It unnecessarily checks substrings longer than `minSize`. If a long substring `sub` is valid and occurs `k` times, its prefix of length `minSize` is also valid and must occur at least `k` times. This insight is missed by this brute-force method.

```java
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {
    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        Map<String, Integer> counts = new HashMap<>();
        int maxOccurrences = 0;

        for (int size = minSize; size <= maxSize; size++) {
            for (int i = 0; i <= s.length() - size; i++) {
                String sub = s.substring(i, i + size);
                if (hasValidUniqueChars(sub, maxLetters)) {
                    counts.put(sub, counts.getOrDefault(sub, 0) + 1);
                    maxOccurrences = Math.max(maxOccurrences, counts.get(sub));
                }
            }
        }
        return maxOccurrences;
    }

    private boolean hasValidUniqueChars(String s, int maxLetters) {
        Set<Character> unique = new HashSet<>();
        for (char c : s.toCharArray()) {
            unique.add(c);
        }
        return unique.size() <= maxLetters;
    }
}
```
### Algorithm
- Initialize a `HashMap<String, Integer>` to store the frequency of all valid substrings and an integer `maxOccurrences` to 0.
- Loop through each possible length `size` from `minSize` to `maxSize`.
- For each `size`, loop through the string `s` from index `i = 0` to `s.length() - size`.
- Extract the substring `sub = s.substring(i, i + size)`.
- Count the number of unique characters in `sub`. A helper function using a `HashSet` or a frequency array can be used for this.
- If the count of unique characters is less than or equal to `maxLetters`, increment the count for `sub` in the HashMap and update `maxOccurrences` with the new count if it's greater.
- After all loops complete, return `maxOccurrences`.

## Optimized Iteration with minSize Substrings
This approach is based on the key observation that the maximum frequency will always be found among substrings of length `minSize`. If a longer substring is valid and occurs `C` times, its `minSize`-length prefix is also valid and occurs at least `C` times. This allows us to ignore `maxSize` and only check substrings of length `minSize`.
**Time:** O(N * minSize). The main loop runs `O(N)` times. Inside the loop, creating the substring, counting its unique characters, and hashing it for the map each take `O(minSize)` time. · **Space:** O(K * minSize), where `K` is the number of unique valid substrings of length `minSize`. In the worst case, `K` can be `O(N)`, leading to `O(N * minSize)` space.
**Pros:** Much more efficient than the first approach by correctly identifying that only `minSize` substrings matter.; Passes the time limits for the given constraints.
**Cons:** Still performs redundant work by re-calculating the number of unique characters for each overlapping substring from scratch.
### Explanation
This approach leverages a critical insight: if a substring `sub` of length `k > minSize` occurs `C` times, any of its prefixes of length `minSize` must occur at least `C` times. For example, if "aaba" occurs once, "aab" must occur at least once. This means the maximum frequency will always be associated with a substring of the minimum possible size, `minSize`.

Therefore, we can completely ignore `maxSize` and only search for valid substrings of length `minSize`.

The algorithm iterates through the string `s` just once, considering all substrings of length `minSize`. For each such substring, it checks its validity (number of unique characters) and updates its frequency in a `HashMap`.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        Map<String, Integer> counts = new HashMap<>();
        int maxOccurrences = 0;

        for (int i = 0; i <= s.length() - minSize; i++) {
            String sub = s.substring(i, i + minSize);
            if (hasValidUniqueChars(sub, maxLetters)) {
                counts.put(sub, counts.getOrDefault(sub, 0) + 1);
                maxOccurrences = Math.max(maxOccurrences, counts.get(sub));
            }
        }
        return maxOccurrences;
    }

    private boolean hasValidUniqueChars(String s, int maxLetters) {
        int[] charCounts = new int[26];
        int unique = 0;
        for (char c : s.toCharArray()) {
            if (charCounts[c - 'a'] == 0) {
                unique++;
            }
            charCounts[c - 'a']++;
        }
        return unique <= maxLetters;
    }
}
```
### Algorithm
- Initialize a `HashMap<String, Integer>` to store substring frequencies and an integer `maxOccurrences` to 0.
- Loop through the string `s` from index `i = 0` to `s.length() - minSize`.
- In each iteration, extract the substring `sub = s.substring(i, i + minSize)`.
- Check if `sub` is valid by counting its unique characters. A helper function that uses a frequency array is efficient for this.
- If the number of unique characters is less than or equal to `maxLetters`, increment its count in the HashMap and update `maxOccurrences` if the new count is larger.
- After the loop, return `maxOccurrences`.

## Sliding Window
This is the most efficient approach. It also focuses only on substrings of length `minSize` but optimizes the validity check. Instead of re-calculating unique characters for each substring, it maintains a 'sliding window' of size `minSize` and updates the unique character count in O(1) time as the window slides.
**Time:** O(N * minSize). The loop runs `O(N)` times. Updating the window state is `O(1)`. However, `substring()` and HashMap operations on the string key still take `O(minSize)`. Despite the same asymptotic complexity as the previous approach, this method is faster in practice. · **Space:** O(K * minSize), where `K` is the number of unique valid substrings of length `minSize`. The window itself uses `O(1)` space. The HashMap dominates the space complexity.
**Pros:** The most performant solution in practice due to O(1) updates for unique character counts per slide.; It's the standard and optimal way to solve this type of substring problem.
**Cons:** The asymptotic time complexity is still bound by substring creation and hashing, which is O(minSize) for each valid window.
### Explanation
This approach is the most efficient and builds upon the previous one. It also focuses only on substrings of length `minSize` but optimizes the process of checking validity. Instead of re-calculating unique characters for each substring, it maintains a 'sliding window' of size `minSize`.

As the window slides one position to the right, we efficiently update the count of unique characters in `O(1)` time by adding the new character and removing the one that falls off the left edge.

A frequency array (`int[26]`) is used to track character counts within the window, and a separate counter tracks the number of unique characters (those with a count > 0).

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        Map<String, Integer> occurrences = new HashMap<>();
        int maxFreq = 0;
        int n = s.length();
        int[] windowChars = new int[26];
        int uniqueCount = 0;
        int start = 0;

        for (int end = 0; end < n; end++) {
            char charEnd = s.charAt(end);
            if (windowChars[charEnd - 'a'] == 0) {
                uniqueCount++;
            }
            windowChars[charEnd - 'a']++;

            // Shrink window if its size is greater than minSize
            if (end - start + 1 > minSize) {
                char charStart = s.charAt(start);
                windowChars[charStart - 'a']--;
                if (windowChars[charStart - 'a'] == 0) {
                    uniqueCount--;
                }
                start++;
            }

            // If the current window is valid, record its occurrence
            if (end - start + 1 == minSize) {
                if (uniqueCount <= maxLetters) {
                    String sub = s.substring(start, end + 1);
                    int count = occurrences.getOrDefault(sub, 0) + 1;
                    occurrences.put(sub, count);
                    maxFreq = Math.max(maxFreq, count);
                }
            }
        }
        return maxFreq;
    }
}
```
### Algorithm
- Initialize a `HashMap<String, Integer> occurrences`, `maxFreq = 0`, a window character count array `windowChars[26]`, and `uniqueCount = 0`.
- Use two pointers, `start` and `end`, to define the sliding window.
- Iterate `end` from `0` to `s.length() - 1`.
- **Add character:** Add `s.charAt(end)` to the window. Update `windowChars` and `uniqueCount`.
- **Shrink window:** If the window size (`end - start + 1`) is greater than `minSize`, shrink it from the left by incrementing `start`. Update `windowChars` and `uniqueCount` for the character `s.charAt(start)` being removed.
- **Process window:** If the window size is exactly `minSize` and `uniqueCount <= maxLetters`, the substring is valid. Extract it, update its count in the `occurrences` map, and update `maxFreq`.
- Return `maxFreq` after the loop.

# Solutions
### Java

```java
class Solution {
public
  int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
    int ans = 0;
    Map<String, Integer> cnt = new HashMap<>();
    for (int i = 0; i < s.length() - minSize + 1; ++i) {
      String t = s.substring(i, i + minSize);
      Set<Character> ss = new HashSet<>();
      for (int j = 0; j < minSize; ++j) {
        ss.add(t.charAt(j));
      }
      if (ss.size() <= maxLetters) {
        cnt.put(t, cnt.getOrDefault(t, 0) + 1);
        ans = Math.max(ans, cnt.get(t));
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
    int ans = 0;
    unordered_map<string, int> cnt;
    for (int i = 0; i < s.size() - minSize + 1; ++i) {
      string t = s.substr(i, minSize);
      unordered_set<char> ss(t.begin(), t.end());
      if (ss.size() <= maxLetters) {
        ans = max(ans, ++cnt[t]);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int: ans = 0 cnt = Counter() for i in range(len(s) - minSize + 1): t = s[i: i + minSize] ss = set(t) if len(ss) <= maxLetters: cnt[t] += 1 ans = max(ans, cnt[t]) return ans

```