Maximum Number of Occurrences of a Substring

You're given a string s and three integers maxLetters, minSize and maxSize.

A substring of s qualifies if:

• it contains at most maxLetters distinct characters, and
• its length is between minSize and maxSize, inclusive.

Return the largest number of times any single qualifying substring occurs in s. Occurrences may overlap: in "aaaa", the substring "aa" occurs 3 times. If no substring qualifies, return 0.

The key observation is that maxSize doesn't matter. Take any qualifying substring t longer than minSize. Every place t occurs, its first minSize characters occur too, and that shorter prefix has no more distinct letters than t. So the prefix qualifies and appears at least as often as t. The best answer is always achieved by some substring of length exactly minSize.

That turns the problem into: slide a window of length minSize across s, keep a count of each letter in the window to know how many distinct letters it has, and tally every window that has at most maxLetters distinct letters. The answer is the highest tally.

def max_freq(s: str, max_letters: int, min_size: int, max_size: int) -> int:
    # A longer qualifying substring always has a qualifying prefix of length
    # min_size that occurs at least as often, so max_size never matters.
    letters = Counter()
    tally = Counter()
    for right, ch in enumerate(s):
        letters[ch] += 1
        left = right - min_size
        if left >= 0:
            letters[s[left]] -= 1
            if letters[s[left]] == 0:
                del letters[s[left]]
        if right >= min_size - 1 and len(letters) <= max_letters:
            tally[s[right - min_size + 1 : right + 1]] += 1
    return max(tally.values(), default=0)

function maxFreq(s, maxLetters, minSize, maxSize) {
  // A longer qualifying substring always has a qualifying prefix of length
  // minSize that occurs at least as often, so maxSize never matters.
  const letters = new Array(26).fill(0);
  let distinct = 0;
  const tally = new Map();
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    if (letters[s.charCodeAt(right) - 97]++ === 0) distinct++;
    const left = right - minSize;
    if (left >= 0 && --letters[s.charCodeAt(left) - 97] === 0) distinct--;
    if (right >= minSize - 1 && distinct <= maxLetters) {
      const sub = s.slice(right - minSize + 1, right + 1);
      const c = (tally.get(sub) || 0) + 1;
      tally.set(sub, c);
      if (c > best) best = c;
    }
  }
  return best;
}

The interviewer is mostly listening for the maxSize argument. State it as a short proof: "any qualifying longer substring has a qualifying prefix of length minSize that occurs at least as many times." Saying that crisply matters more than the code.

Then describe the sliding window and say how you track distinct letters in O(1) per step. If asked about hashing cost, mention that substrings of length minSize are at most 26 characters, or that a rolling hash removes the slicing cost entirely.