Leetcode 1297. Maximum Number of Occurrences of a Substring

Problem Explanation

This problem requires us to determine the maximum number of occurrences of any substring in a given string. The problem statement has some restrictions, such as the number of unique characters in the substring cannot exceed a given maxLetters, and the size of the substring must fall between minSize and maxSize (both inclusive).

Here's an illustration of the problem using an example:

Let's take the string s = "aababcaab" with maxLetters = 2, minSize = 3 and maxSize = 4. In this string, the substring aab occurs twice. Here, aab meets all our conditions – it contains only 2 unique letters (which is less than or equal to maxLetters), and its length is 3 (which lies between minSize and maxSize). So, the maximum number of occurrences of any substring is 2.

Approach Explanation

The solution to this problem involves a greedy approach and uses the sliding window technique of string manipulation. And we don't need the maxSize, because using a substring less than maxSize but greater than or equal to minSize will always increase the frequency of substrings.

Firstly, we initialize our result variable ans = 0, count of letters letters = 0, and also have two arrays – one to keep count of character frequencies and another to keep track of the count of substrings.

We further use two pointers to start and end our substring. We firstly increase our end pointer and add the frequency of the character pointed by end to our count array. If it's the first occurrence of the current character, we increase our letters.

As we go forward, we continually check if our letters exceed maxLetters or our substring length exceeds minSize. If it does, we decrease our letters and start.

Finally, if our substring length is equal to minSize, we can add this substring to our substringCount and update our result answer.

Python Solution

1
2python
3class Solution:
4    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
5        # Ignoring maxSize, just consider strings with minSize as the greedy approach
6        ans = 0
7        letters = 0
8        count = [0] * 26
9        substringCount = {}
10
11        for start in range(len(s) - minSize + 1):
12            # Each new substring, rewind letters and count
13            if start == 0:
14                for i in range(minSize):
15                    if count[ord(s[i]) - ord('a')] == 0:
16                        letters += 1
17                    count[ord(s[i]) - ord('a')] += 1
18            else:
19                # remove first letter of the last substring
20                if count[ord(s[start - 1]) - ord('a')] == 1:
21                    letters -= 1
22                count[ord(s[start - 1]) - ord('a')] -= 1
23                
24                # add new letter
25                if count[ord(s[start + minSize - 1]) - ord('a')] == 0:
26                    letters += 1
27                count[ord(s[start + minSize - 1]) - ord('a')] += 1
28            
29            # Add to dict if no. of unique letters is <= maxLetters
30            if letters <= maxLetters:
31                substringCount[s[start:start + minSize]] = substringCount.get(s[start:start + minSize], 0) + 1
32                ans = max(ans, substringCount[s[start:start + minSize]])
33                
34        return ans

Java Solution

1
2java
3class Solution {
4    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
5        int ans = 0;
6        int letters = 0;
7        int[] count = new int[26];
8        Map<String, Integer> substringCount = new HashMap<>();
9
10        for (int start = 0; start + minSize <= s.length(); start++) {
11            String substring = s.substring(start, start + minSize);
12            if (start == 0 || !substring.startsWith(s.substring(start - 1, start))) {
13                count = new int[26];
14                for (int i = start; i < start + minSize; i++)
15                    count[s.charAt(i) - 'a']++;
16                letters = 0;
17                for (int freq : count)
18                    if (freq > 0)
19                        letters++;
20            } else if (--count[s.charAt(start - 1) - 'a'] == 0)
21                letters--;
22            if (letters <= maxLetters)
23                ans = Math.max(ans, substringCount.merge(substring, 1, Integer::sum));
24        }
25
26        return ans;
27    }
28}

Javascript Solution

1
2javascript
3var maxFreq = function(s, maxLetters, minSize, maxSize) {
4    // Ignore maxSize, just consider strings with minSize
5    let ans = 0;
6    let letters = 0;
7    let count = Array(26).fill(0);
8    let substringCount = {};
9
10    // Iterate through the string with fixed size of minSize
11    for( let start = 0; start + minSize <= s.length; start++){
12        let substring = s.slice(start, start+minSize);
13        if(start == 0 || !substring.startsWith(s[start - 1])) {
14            count.fill(0);
15            for(let i = start; i < start+minSize ; i++)
16                count[s.charCodeAt(i) - 'a'.charCodeAt()]++;
17            letters = 0;
18            for(let freq of count)
19                if(freq > 0)
20                    letters++;
21        } else if (--count[s.charCodeAt(start - 1) - 'a'.charCodeAt()] === 0)
22            letters--;
23        if(letters <= maxLetters)
24            ans = Math.max(ans, substringCount[substring] = (substringCount[substring] || 0) + 1);
25    }
26
27    return ans;
28};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
6        unordered_map<string, int> count;
7        int max_occur = 0;
8        for (int i = 0; i <= s.size() - minSize; ++ i) {
9            ++ count[s.substr(i, minSize)];
10            if (i > 0) {
11                char last = s[i + minSize - 1];
12                if (s[i - 1] == last) continue;
13                unordered_map<char, int> chars;
14                for (char c : s.substr(i, minSize))
15                    ++ chars[c];
16                if (chars.size() <= maxLetters) max_occur = max(max_occur, count[s.substr(i, minSize)]);
17            } else {
18                unordered_map<char, int> chars;
19                for (char c : s.substr(i, minSize))
20                    ++ chars[c];
21                if (chars.size() <= maxLetters) max_occur = max(max_occur, count[s.substr(i, minSize)]);
22            }
23        }
24        return max_occur;
25    }
26};

C# Solution

1
2csharp
3public class Solution {
4    public int MaxFreq(string s, int maxLetters, int minSize, int maxSize) {
5        var map = new Dictionary<string, int>();
6        var maxOcurrences = 0;
7        
8        for (int i = 0; i <= s.Length - minSize; i++) 
9        {
10            var substring = s.Substring(i, minSize);
11            var charSet = new HashSet<char>(substring);
12            
13            if (charSet.Count <= maxLetters) 
14            {
15                if (!map.ContainsKey(substring)) 
16                {
17                    map[substring] = 0;
18                }
19                map[substring]++;
20                maxOcurrences = Math.Max(maxOcurrences, map[substring]);
21            }
22        }
23        return maxOcurrences;
24    }
25}

In the solution above, the HashMap map stores the counts of substrings, and the HashSet charSet stores the unique characters present in each substring. We iterate through the string and store the counts of substrings, but only if they satisfy the given conditions. At the end of the loop, we return the maximum number of occurences.Ruby Solution

1
2ruby
3def max_freq(s, max_letters, min_size, max_size)
4  hash_map = Hash.new(0)  # create a new hash
5  max_freq = 0
6  s.chars.each_cons(min_size) do |substring|  # iterate through the array of characters with each consecutive substring
7    next if substring.uniq.length > max_letters  # if the number of unique letters in the substring exceeds max_letters
8    str = substring.join  # join the characters in the current substring
9    hash_map[str] += 1  # increment the current substring
10    max_freq = [max_freq, hash_map[str]].max  # find the max frequency
11  end
12  max_freq  # returns max_freq
13end

In the Ruby solution, we use Ruby's Hash#new method that creates a new hash. Then we create an array of unique characters in s using chars method and iterate through this array with each_cons method. This method iterates the given block for each array of consecutive n elements, where n is our min_size. In the block, we skip to the next iteration if the number of unique letters in the substring is more than max_letters. Finally, we join the substring and increment its frequency in the hash, and keep track of the maximum frequency encountered so far.

GoLang Solution

1
2go
3func maxFreq(s string, maxLetters int, minSize int, maxSize int) int {
4    counts := map[string]int{}
5    high := 0
6    letter_count := make(map[rune]int)
7    for i := 0; i < minSize-1; i++ {
8        letter_count[rune(s[i])]++
9    }
10    for i := minSize-1; i < len(s); i++ {
11        letter_count[rune(s[i])]++
12        if len(letter_count) <= maxLetters {
13            str := s[i-minSize+1 : i+1]
14            counts[str] += 1
15            if counts[str] > high {
16                high = counts[str]
17            }
18        }
19        letter_count[rune(s[i-minSize+1])]--
20        if letter_count[rune(s[i-minSize+1])] == 0 {
21            delete(letter_count, rune(s[i-minSize+1]))
22        }
23    }
24    return high
25}

In the Golang solution, we create a letter_count map with character frequency and iterate over the string s. For each character, we increment its count in letter_count. If number of unique letters doesn't exceed maxLetters, we count the occurrence of the substring and keep track of the highest frequency. Lastly, we decrement the count of the first character of the substring in letter_count and if its count reaches zero, we remove it from the map.

These solutions all share a similar strategy - they slide a window of predefined size (minSize) across the input string, and record the maximum frequency of a valid substring that meets the constraints defined in the problem. The solutions vary by language due to differing syntax and available standard library methods, but conceptual approach remains the same across all implementations.