Scale Engineer

Maximum Number of Occurrences of a Substring

Med
#1208Time: O((maxSize - minSize) * N * L), where `L` is the substring length. The nested loops run `(maxSize - minSize) * N` times. Inside, substring creation and unique character counting each take `O(L)`. This is very inefficient.Space: O(K * L), where `K` is the number of unique valid substrings and `L` is their average length. In the worst case, this can be `O(N * L)`.3 companies
Patterns
Sliding Window
Data structures
Hash TableString
Companies
AtlassianHubspotRoblox

Prompt

Given a string s, return the maximum number of occurrences 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 occurrences 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.

 

Constraints:

  • 1 <= s.length <= 105
  • 1 <= maxLetters <= 26
  • 1 <= minSize <= maxSize <= min(26, s.length)
  • s consists of only lowercase English letters.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach iterates through all possible substring lengths from minSize to maxSize. For each length, it generates all substrings, checks if they are valid (i.e., have at most maxLetters unique characters), and counts their occurrences using a HashMap.

Algorithm

  • Initialize a HashMap<String, Integer> to store the frequency of all valid substrings and an integer maxOccurrences to 0.
  • Loop through each possible length size from minSize to maxSize.
  • For each size, loop through the string s from index i = 0 to s.length() - size.
  • Extract the substring sub = s.substring(i, i + size).
  • Count the number of unique characters in sub. A helper function using a HashSet or a frequency array can be used for this.
  • If the count of unique characters is less than or equal to maxLetters, increment the count for sub in the HashMap and update maxOccurrences with the new count if it's greater.
  • After all loops complete, return maxOccurrences.

Walkthrough

This approach directly translates the problem statement into code without any optimization. It considers every possible substring that fits the length criteria (minSize to maxSize).

It uses nested loops. The outer loop iterates through all possible substring lengths from minSize to maxSize. The inner loop iterates through the string s to generate all substrings of the current length.

For each generated substring, a helper function is called to count its unique characters. If this count is within the maxLetters limit, the substring is considered valid.

A HashMap is used to store each unique valid substring and its frequency. After checking all possible substrings, the maximum frequency stored in the map is returned.

The main drawback is its performance. It unnecessarily checks substrings longer than minSize. If a long substring sub is valid and occurs k times, its prefix of length minSize is also valid and must occur at least k times. This insight is missed by this brute-force method.

import java.util.HashMap;import java.util.HashSet;import java.util.Map;import java.util.Set; class Solution {    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {        Map<String, Integer> counts = new HashMap<>();        int maxOccurrences = 0;         for (int size = minSize; size <= maxSize; size++) {            for (int i = 0; i <= s.length() - size; i++) {                String sub = s.substring(i, i + size);                if (hasValidUniqueChars(sub, maxLetters)) {                    counts.put(sub, counts.getOrDefault(sub, 0) + 1);                    maxOccurrences = Math.max(maxOccurrences, counts.get(sub));                }            }        }        return maxOccurrences;    }     private boolean hasValidUniqueChars(String s, int maxLetters) {        Set<Character> unique = new HashSet<>();        for (char c : s.toCharArray()) {            unique.add(c);        }        return unique.size() <= maxLetters;    }}

Complexity

Time

O((maxSize - minSize) * N * L), where `L` is the substring length. The nested loops run `(maxSize - minSize) * N` times. Inside, substring creation and unique character counting each take `O(L)`. This is very inefficient.

Space

O(K * L), where `K` is the number of unique valid substrings and `L` is their average length. In the worst case, this can be `O(N * L)`.

Trade-offs

Pros

  • Simple to understand and implement as it's a direct interpretation of the problem statement.

Cons

  • Highly inefficient due to redundant computations and checking unnecessary substring lengths.

  • Likely to result in a 'Time Limit Exceeded' error on larger inputs.

Solutions

class Solution {public  int maxFreq(String s, int maxLetters, int minSize, int maxSize) {    int ans = 0;    Map<String, Integer> cnt = new HashMap<>();    for (int i = 0; i < s.length() - minSize + 1; ++i) {      String t = s.substring(i, i + minSize);      Set<Character> ss = new HashSet<>();      for (int j = 0; j < minSize; ++j) {        ss.add(t.charAt(j));      }      if (ss.size() <= maxLetters) {        cnt.put(t, cnt.getOrDefault(t, 0) + 1);        ans = Math.max(ans, cnt.get(t));      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem