Maximum Number of Occurrences of a Substring

Medium
647.

Maximum Number of Occurrences of a Substring

Maximum Number of Occurrences of a Substring is a medium coding problem on strings, hash table and sliding window, asked in Amazon, Google and Microsoft interviews.

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)
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} maxLetters
 * @param {number} minSize
 * @param {number} maxSize
 * @return {number}
 */
var maxFreq = function(s, maxLetters, minSize, maxSize) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Number of Occurrences of a Substring — Solution

Maximum Number of Occurrences of a Substring solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Number of Occurrences of a Substring is a medium coding problem on strings, hash table and sliding window, asked in Amazon, Google and Microsoft interviews.

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)

Hints for Maximum Number of Occurrences of a Substring

  1. Hint 1

    maxSize is a red herring. Why would a longer substring ever beat a shorter one?

  2. Hint 2

    Any occurrence of a longer valid substring contains an occurrence of its length-minSize prefix, which is also valid.

  3. Hint 3

    So only windows of exactly minSize need counting.

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

Java

public static int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
    Map<String, Integer> count = new HashMap<>();
    int best = 0;
    for (int i = 0; i + minSize <= s.length(); i++) {
        String sub = s.substring(i, i + minSize);
        Set<Character> seen = new HashSet<>();
        for (int j = 0; j < sub.length(); j++) seen.add(sub.charAt(j));
        if (seen.size() > maxLetters) continue;
        int c = count.getOrDefault(sub, 0) + 1;
        count.put(sub, c);
        if (c > best) best = c;
    }
    return best;
}

C++

int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
    unordered_map<string, int> count;
    int best = 0;
    for (int i = 0; i + minSize <= (int) s.size(); i++) {
        string sub = s.substr(i, minSize);
        vector<bool> seen(26, false);
        int distinct = 0;
        for (char c : sub) {
            if (!seen[c - 'a']) { seen[c - 'a'] = true; distinct++; }
        }
        if (distinct > maxLetters) continue;
        int c = ++count[sub];
        if (c > best) best = c;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets