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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.