Given a string s, return the maximum number of ocurrences 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 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.
Example 3:
Input: s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3
Output: 3
Example 4:
Input: s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
Output: 0
Constraints:
1 <= s.length <= 10^5
1 <= maxLetters <= 26
1 <= minSize <= maxSize <= min(26, s.length)
s only contains lowercase English letters.
Solution:
Approach 1:
class Solution {
public int maxFreq(String s, int maxLetters, int minSize, int maxSize)
{
if(s == null || s.length() == 0 || maxLetters == 0) return 0;
HashMap<String, Integer> hm = new HashMap<>();
int max = 0;
for(int i = 0; i < s.length() - minSize + 1; i++) {
String cur = s.substring(i, i + minSize);
if(isValid(cur, maxLetters,maxSize)) {
hm.put(cur, hm.getOrDefault(cur, 0) + 1);
max = Math.max(max, hm.get(cur));
}
}
return max;
}
boolean isValid(String cur, int maxLetters,int maxsize)
{
HashSet<Character> hs = new HashSet<>();
for(char c: cur.toCharArray()) hs.add(c);
return hs.size() <= maxLetters && cur.length()<=maxsize;
}
}Approach 2:
class Solution {
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
int[] ch = new int[26];
int Letters=0,NoOfOccurrence=0;
Map<String,Integer> map = new HashMap<>();
for(int i=0,j=0;i<s.length();i++) {
char c = s.charAt(i);
if(++ch[c-'a']==1) {
Letters++;
}
while(Letters>maxLetters || i-j+1>maxSize) {
if(--ch[s.charAt(j)-'a']==0) Letters--;
j++;
}
while(i-j+1>=minSize) {
String s1=s.substring(j,i+1);
map.put(s1,map.getOrDefault(s1,0)+1);
NoOfOccurrence=Math.max(NoOfOccurrence,map.get(s1));
if(--ch[s.charAt(j)-'a']==0) Letters--;
j++;
}
}
return NoOfOccurrence;
}
}