Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1297.html

1297. Maximum Number of Occurrences of a Substring

Level

Medium

Description

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

Let length be the length of the given string s, for a substring with length between minSize and maxSize inclusive, the start index of the substring is between 0 and length - minSize inclusive.

For each start index, consider all possible substrings with length between minSize and maxSize inclusive (if the start index is large, then it is possible that the maximum length of the substring is less than maxSize). If the unique characters in the substring is less than or equal to maxLetters, then update the number of ocurrences of the substring. Otherwise, no more substrings starting with the current start index will satisfy the rules (the existent characters won’t be deleted, and new characters will be added for longer substrings), so go to the next start index.

Use a Map to store the number of ocurrences of each substring. Also use a Map to store the number of unique characters in the current substring.

After all substrings are considered, iterate over the Map that stores the number of ocurrences of each substring, and get the maximum number of occurrences and return.

• Java
• C++
• Python

• class Solution {
      public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
          Map<String, Integer> substringCountsMap = new HashMap<String, Integer>();
          int length = s.length();
          int maxBegin = length - minSize;
          for (int i = 0; i <= maxBegin; i++) {
              Map<Character, Integer> lettersCountMap = new HashMap<Character, Integer>();
              boolean flag = true;
              for (int j = 0; j < minSize - 1; j++) {
                  char c = s.charAt(i + j);
                  int count = lettersCountMap.getOrDefault(c, 0);
                  count++;
                  lettersCountMap.put(c, count);
                  if (lettersCountMap.keySet().size() > maxLetters) {
                      flag = false;
                      break;
                  }
              }
              if (!flag)
                  continue;
              for (int j = i + minSize; j <= Math.min(i + maxSize, length); j++) {
                  char curC = s.charAt(j - 1);
                  int count = lettersCountMap.getOrDefault(curC, 0);
                  count++;
                  lettersCountMap.put(curC, count);
                  if (lettersCountMap.keySet().size() > maxLetters) {
                      flag = false;
                      break;
                  }
                  String substring = s.substring(i, j);
                  int substringCount = substringCountsMap.getOrDefault(substring, 0);
                  substringCount++;
                  substringCountsMap.put(substring, substringCount);
              }
          }
          Set<String> substringSet = substringCountsMap.keySet();
          int maxCount = 0;
          for (String substring : substringSet) {
              int count = substringCountsMap.getOrDefault(substring, 0);
              maxCount = Math.max(maxCount, count);
          }
          return maxCount;
      }
  }
  

• // OJ: https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/
  // Time: O(N)
  // Space: O(N)
  class Solution {
  public:
      int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
          unsigned h = 0, p = 1, d = 16777619, ans = 0;
          unordered_map<unsigned, unsigned> cnt, m;
          for (int i = 0; i < s.size(); ++i) {
              h = h * d + s[i] - 'a';
              m[s[i]]++;
              if (i < minSize) {
                  p *= d;
              }
              if (i >= minSize) {
                  h -= p * (s[i - minSize] - 'a');
                  if (--m[s[i - minSize]] == 0) m.erase(s[i - minSize]);
              }
              if (i >= minSize - 1 && m.size() <= maxLetters) {
                  ans = max(ans, ++cnt[h]);
              }
          }
          return ans;
      }
  };
  

• class Solution:
      def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
          ans = 0
          cnt = Counter()
          for i in range(len(s) - minSize + 1):
              t = s[i : i + minSize]
              ss = set(t)
              if len(ss) <= maxLetters:
                  cnt[t] += 1
                  ans = max(ans, cnt[t])
          return ans
  
  ############
  
  # 1297. Maximum Number of Occurrences of a Substring
  # https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/
  
  class Solution:
      def maxFreq(self, s: str, maxLetters: int, k: int, maxSize: int) -> int:
          count = collections.Counter()
          
          for i in range(len(s) - k + 1):
              count[s[i:i+k]] += 1
          
          return max([count[w] for w in count if len(set(w)) <= maxLetters] + [0])
  

All Problems

All Solutions