# Maximum Number of Occurrences of a Substring Leetcode Solution

Difficulty Level Medium

## Problem Statement :

Maximum Number of Occurrences of a Substring Leetcode Solution – 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 :

### 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.

## Observation :

•  In the given problem, we have to return the maximum number of occurrences of any substring that obeys the given rules.
• Our most basic approach will be to check occurrences of substrings of minSize to maxSize and count their occurrences using a map.
•  If we look closely, each occurrence of a substring with a length more than minSize will actually encompass a string of minSize itself, therefore we just need to check and count the frequency of minSize substrings.
• So, we can easily use a sliding window of that size and check for the constraints within that window.
• Checking for rules in the current substring can be done in O(n) by using a hashmap to store the unique count of characters in the window.
•  The key here is to understand that we don’t need to care about maxSize.

## Algorithm :

• First, we’ll initialize two frequency maps. One map ( freqMap ) will store the character frequency of String s and through this character frequency map we will check the unique character constraint, and the other will store the string frequency (ansFreqMap).
• We will use two pointers i and ji will help us to acquire the characters of s, and j will help us to release the characters of s.
• Now, run a loop to create a window of size minSize-1 and put the characters in the freqMap.
• Now, run the second loop, in this loop, we will acquire a character of s by acquiring pointer (i) and store that character in freqMap.
• After acquiring a character we have a window of minSize so we will check that our current substring follows the unique letter constraint ( The number of unique characters in the substring must be less than or equal to maxLetters ).
• If the current substring follows all the given rules then we will store the substring in ansFreqMap.
• Now increment the releasing pointer ( j ) and release the  character where releasing pointer ( j ) points from freqMap
• At last, we will find the max frequency of substring present in the ansFreqMap.

## Code for Maximum Number of Occurrences of a Substring :

### Java  Code

//no of uq ch <=maxLetters
//length of minsize<=sub>=maxsize

class Solution {
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
int n=s.length();
Map<Character,Integer>freqMap=new HashMap<>();
Map<String,Integer>ansFreqMap=new HashMap<>();
int countOfUniqueChar=0;
int ans=0;
int i=0;
int j=-1;
for(;i<minSize-1;i++){
char ch=s.charAt(i);
freqMap.put(ch,freqMap.getOrDefault(ch,0)+1);
}
i--;
while(i<n-1){
i++;
char ch=s.charAt(i);
freqMap.put(ch,freqMap.getOrDefault(ch,0)+1);
countOfUniqueChar=freqMap.size();
if(countOfUniqueChar<=maxLetters){
String sub= s.substring(j+1,i+1);
ansFreqMap.put(sub,ansFreqMap.getOrDefault(sub,0)+1);
}
j++;
ch=s.charAt(j);
freqMap.put(ch,freqMap.get(ch)-1);
if(freqMap.get(ch)==0)freqMap.remove(ch);

}
for(String key:ansFreqMap.keySet()){
int freqVal=ansFreqMap.get(key);
ans=Math.max(ans,freqVal);
}
return ans;

}
}

### C++  Code

class Solution {
public:
int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
int n=s.size();
// To store  frequency of characters in string s
unordered_map<char,int>freqMap;
// To store  Substring of string s with given constraint of size minSize
unordered_map<string,int>ansFreqMap;
//tells us about unique characters in string s
int countOfUniqueChar=0;
int ans=0;
// i -> for acquiring
int i=0;
//j->for relasing
int j=-1;
// acquire till less than minsize-1
for(;i<minSize-1;i++){
char ch=s[i];
freqMap[ch]++;
}
i--;
//now make the minSize window by acquring and relasing
while(i<n-1){
i++;
char ch=s[i];
freqMap[ch]++;
countOfUniqueChar=freqMap.size();
if(countOfUniqueChar<=maxLetters){
string sub= s.substr(j+1,i-j);
ansFreqMap[sub]++;
}
j++;
ch=s[j];
freqMap[ch]--;
if(freqMap[ch]==0)freqMap.erase(ch);

}

for(auto key:ansFreqMap){
int freqVal=key.second;
ans=max(ans,freqVal);
//cout<<key.first<<" "<<key.second<<endl;
}
//cout<<ansFreqMap.size()<<endl;
return ans;

}
};

## Complexity Analysis for Maximum Number of Occurrences of a Substring Leetcode Solution

### Time Complexity

O(n), where n  is the length of the string

O(n).

Translate »