Get started

Maximum Number of Occurrences of a Substring — Medium Problem & Solution

Given a string s, return the maximum number of occurrences of any substring that satisfies both rules: it contains at most maxLetters distinct characters;…

Problem statement

Given a string s, return the maximum number of occurrences of any substring that satisfies both rules:

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

If no substring qualifies, return 0.

Example 1

Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
Output: 2
Explanation: "aab" occurs twice and has two distinct letters.

Example 2

Input: s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
Output: 2
Explanation: "aaa" occurs at indices 0 and 1.

Example 3

Input: s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
Output: 0

Constraints

  • 1 <= s.length <= 100000
  • 1 <= maxLetters <= 26
  • 1 <= minSize <= maxSize <= min(26, s.length)

How to solve Maximum Number of Occurrences of a Substring

Only length minSize matters. A substring of length L > minSize that occurs k times has a prefix of length minSize occurring at least k times, with no more distinct letters — so the shortest allowed window always ties or wins.

Approach

  1. Slide a window of exactly minSize characters across s.
  2. For each window, count its distinct characters and skip it if that exceeds maxLetters.
  3. Tally the window's text in a hash map and keep the running maximum tally.

Why it works

Every occurrence of a longer valid substring yields an occurrence of its minSize prefix at the same start, so the prefix's count is at least as large; and a prefix has a subset of the letters, so it is still within maxLetters. The maximum over length-minSize windows is therefore the global maximum.

Complexity

  • Time — O(n · minSize)
  • Space — O(n · minSize)

Pitfalls

  • Enumerating every length from minSize to maxSize is correct but does far more work than needed.
  • Forgetting the distinct-letter check counts substrings that violate maxLetters.

Reference solution

Python

def maxFreq(s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
    count = {}
    best = 0
    for i in range(len(s) - minSize + 1):
        sub = s[i:i + minSize]
        if len(set(sub)) > maxLetters:
            continue
        count[sub] = count.get(sub, 0) + 1
        best = max(best, count[sub])
    return best

JavaScript

var maxFreq = function(s, maxLetters, minSize, maxSize) {
    var count = {}, best = 0;
    for (var i = 0; i + minSize <= s.length; i++) {
        var sub = s.substr(i, minSize);
        var seen = {}, distinct = 0;
        for (var j = 0; j < sub.length; j++) {
            var c = sub.charAt(j);
            if (seen[c] !== true) { seen[c] = true; distinct++; }
        }
        if (distinct > maxLetters) continue;
        count[sub] = (count[sub] === undefined ? 0 : count[sub]) + 1;
        if (count[sub] > best) best = count[sub];
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue