LeetCode [1297] Maximum Number of Occurrences of a Substring

 1297. Maximum Number of Occurrences of a Substring

Medium

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

class Solution { public int maxFreq(String s, int maxLetters, int minSize, int maxSize) { Map<String, Integer> cntW = new HashMap<>(); int[] cntL = new int[26]; int unqL = 0; int maxCnt = 0; int i = 0, j = 0, n = s.length(); while(j<n){ int c = s.charAt(j)-'a'; if(cntL[c]==0) unqL++; cntL[c]++; while(j-i+1>maxSize || unqL>maxLetters){ c = s.charAt(i)-'a'; cntL[c]--; if(cntL[c]==0) unqL--; i++; } while(j-i+1>=minSize){ String sub = s.substring(i, j+1); cntW.put(sub, cntW.getOrDefault(sub, 0)+1); // System.out.println(sub+" "+cntW.get(sub)); if(cntW.get(sub)>maxCnt) maxCnt = cntW.get(sub); c = s.charAt(i)-'a'; cntL[c]--; if(cntL[c]==0) unqL--; i++; } j++; } return maxCnt; } }