top of page
Search

# Maximum Number of Occurrences of a Substring

Updated: Mar 25, 2021

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<>();
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;
}
}```

See All