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
andmaxSize
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; } } |
No comments:
Post a Comment