TLDR

1. Welcome!

2. 1297. Maximum Number of Occurrences of a Substring

3. Read the most impartial newsletter

4. Recommendations I live by!

5. Self-Gaslight of the week

6. Hacks of the week

Day 30: 1297. Maximum Number of Occurrences of a Substring

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.

Before we dive in,

What would be our naive solution?

If your answer was finding all of the subarrays, you are correct! But you like expensive things. And I’m cheap, so let’s see an optimized solution.

The clue to identifying that it’s a sliding window problem is that you don’t have to compute the sum of each subarray; you can compute the next subarray by modifying any limit (Left or Right pointer) of the previous subarray.

For this problem, you are given a size range rather than a fixed length. But there is a small catch to this, it took me a while to realize but the greediest 🤑 thing to do is to only care about the minSize .

Think about what is more likely:

• Finding an A in a book

• Finding ABCERI in a book

The first option is more likely, let’s save ourselves some coin and only care about the minSize.

Now that we got some clues…

Let’s dive in 🤿 :

We can start by defining the variables that we are going to use.

• fr: A map of subarray frequencies.

• maxFrequency: Holds the maximum frequency of the subarrays that meet our conditions.

• unique: A map, used to ensure the subarray contains only distinct values.

• left: A pointer indicating the start of the window.

• right: A pointer indicating the end of the window.

  The sliding window technique involves iterating through our array using the left and right pointers. right will sliiide through the array (iterate with a for loop).

We are going to do three steps at each step of the iteration.

1. Open the window:

   1. Add the element at right to our unique map

2. Close the window:

   1. If the size of our window is larger than minSize we are no longer interested.

   2. We delete the element at left from our unique map

   3. We delete the element at left from our fr map.

      • Important note, we must eliminate the index from the map if it is not used, otherwise, the index is going to exist with a value of 0 .

3. The window matches our conditions

   1. Add the frequency of that subarray to our fr map.

   2. Compare the frequency of the current subarray to maxElement and update.

Let’s set an example:

Final Answer:

class Solution {
public:
    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
        map<string,int>fr;
        map<char,int>unique; 
        int left=0; 
        int maxFrequency=0; 
        for(int right=0; right<s.length(); right++){
           
            //open window 
             unique[s[right]]++; 
          
            //close the window
            if((right - left + 1 > minSize) ){
                unique[s[left]]--; 
                if(unique[s[left]]==0){
                    unique.erase(s[left]);
                }
                l++;      
            }

            //matches conditions
            if((right-left+1)==minSize && unique.size()<=maxLetters){
               fr[s.substr(left,minSize)]++; 
               maxFrequency = max(fr[s.substr(left,minSize)], maxFrequency); 
            }
        }
       return maxFrequency; 
    }    
};
        }

Recommendations

Level up your inbox by subscribing to what I am subscribed to!

Self-gaslight of the week

I truly believe you can gaslight yourself to success.

1. Become the main character, Taylor Swift is the story’s architect hero, protagonist, and narrator.

2. Talent recognizes talent, Adele paused her Munich concert to show women's 100m final

Hacks of the week

1. Know your O notations!!

2. Do a cheat sheet with all of the patterns before an interview and review them