Maximum Number of Occurrences of a Substring Leetcode Solution

Difficulty Level Medium
Frequently asked in Amazon Atlassian Bloomberg Facebook PayPal Roblox TwitterViews 26

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 :

Maximum Number of Occurrences of a Substring Leetcode SolutionPin

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

Space Complexity 

 O(n).

Translate »