Show problems as
Classic problem #1297MediumHash TableStringSliding Window

Maximum Number of Occurrences of a Substring

Real-world version: Most Repeated Status Signature
Tracked in this browser only
Read Maximum Number of Occurrences of a Substring on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A field controller writes one lowercase letter per tick into a status log, given as the string s. Analysts look for a signature: an unbroken stretch of the log that turns up again and again.

A stretch is only worth reporting when both of these hold:

  • it is built from at most maxLetters different letters;
  • its length is at least minSize and at most maxSize.

A stretch occurs once for every starting position in s at which it appears, so two appearances that overlap are counted separately.

Return the largest number of occurrences achieved by any reportable stretch. If no stretch is reportable, return 0.

Examples

Example 1

Input
s = "aaabaaab", maxLetters = 2, minSize = 2, maxSize = 4
Output
4

The stretch "aa" uses one letter and has length 2, so it is reportable, and it starts at positions 0, 1, 4 and 5, which is four occurrences.

Example 2

Input
s = "efefefg", maxLetters = 2, minSize = 2, maxSize = 3
Output
3

The stretch "ef" uses two letters, which is the limit, and has length 2. It starts at positions 0, 2 and 4, so it occurs three times.

Example 3

Input
s = "abcdef", maxLetters = 1, minSize = 3, maxSize = 4
Output
0

Every stretch of length 3 or 4 in this log uses at least three different letters, which is above the limit of one, so nothing is reportable and the answer is 0.

Constraints

  • 1 <= s.length <= 10^5
  • 1 <= maxLetters <= 26
  • 1 <= minSize <= maxSize <= min(26, s.length)
  • s contains only lowercase English letters.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_freq(s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
Java
public int maxFreq(String s, int maxLetters, int minSize, int maxSize)

More on the same topics