Maximum Number of Occurrences of a Substring Leetcode Solution

Table of Contents

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.

Constraints :

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 j, i 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 $s .$