1297. Maximum Number of Occurrences of a Substring LeetCode Solution
In this guide, you will get 1297. Maximum Number of Occurrences of a Substring LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Occurrences of a Substring problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
Example 1:
Input: s = “aababcaab”, maxLetters = 2, minSize = 3, maxSize = 4
Output: 2
Explanation: Substring “aab” has 2 occurrences 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:
1 <= s.length <= 105
1 <= maxLetters <= 26
1 <= minSize <= maxSize <= min(26, s.length)
s consists of only lowercase English letters.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
1297. Maximum Number of Occurrences of a Substring LeetCode Solution in C++
class Solution {
public:
int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
// Greedily consider strings with `minSize`, so ignore `maxSize`.
int ans = 0;
int letters = 0;
vector<int> count(26);
unordered_map<string, int> substringCount;
for (int l = 0, r = 0; r < s.length(); ++r) {
if (++count[s[r] - 'a'] == 1)
++letters;
while (letters > maxLetters || r - l + 1 > minSize)
if (--count[s[l++] - 'a'] == 0)
--letters;
if (r - l + 1 == minSize)
ans = max(ans, ++substringCount[s.substr(l, minSize)]);
}
return ans;
}
}; /* code provided by PROGIEZ */
1297. Maximum Number of Occurrences of a Substring LeetCode Solution in Java
class Solution {
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
// Greedily consider strings with `minSize`, so ignore `maxSize`.
int ans = 0;
int letters = 0;
int[] count = new int[26];
Map<String, Integer> substringCount = new HashMap<>();
for (int l = 0, r = 0; r < s.length(); ++r) {
if (++count[s.charAt(r) - 'a'] == 1)
++letters;
while (letters > maxLetters || r - l + 1 > minSize)
if (--count[s.charAt(l++) - 'a'] == 0)
--letters;
if (r - l + 1 == minSize)
ans = Math.max(ans, substringCount.merge(s.substring(l, l + minSize), 1, Integer::sum));
}
return ans;
}
} // code provided by PROGIEZ
1297. Maximum Number of Occurrences of a Substring LeetCode Solution in Python
class Solution:
def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
# Greedily consider strings with `minSize`, so ignore `maxSize`.
ans = 0
letters = 0
count = collections.Counter()
substringCount = collections.Counter()
l = 0
for r, c in enumerate(s):
count[c] += 1
if count[c] == 1:
letters += 1
while letters > maxLetters or r - l + 1 > minSize:
count[s[l]] -= 1
if count[s[l]] == 0:
letters -= 1
l += 1
if r - l + 1 == minSize:
sub = s[l:l + minSize]
substringCount[sub] += 1
ans = max(ans, substringCount[sub])
return ans # code by PROGIEZ
