0544MediumHash TableStringSliding Window

Most Repeated Status Signature

Tracked in this browser only

Trains the technique from

LeetCode 1297Maximum Number of Occurrences of a Substring

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O(n * minSize) — each of the n windows is sliced and hashed once, and minSize is at most 26.Space O(n * minSize) for the tally map in the worst case, again with minSize at most 26.

Count only the stretches whose length is exactly `minSize`. Any longer reportable stretch starts with one of those, that shorter start uses no more distinct letters, and it appears at every position where the longer one does, so it can never occur fewer times. So the best count is already reached at the shortest allowed length. Slide a window of that length across the log with a letter-count map, which keeps the number of distinct letters in the window available at each step, and tally the windows that pass the letter limit in a second map keyed by the window text. The answer is the largest tally, or 0 when the tally map stays empty.

Pythonentry point: max_freq

def max_freq(s, maxLetters, minSize, maxSize):
    # Only stretches of the shortest allowed length need counting: a longer
    # qualifying stretch begins with a stretch of length minSize that uses no
    # more letters and starts wherever the longer one does, so it occurs at
    # least as often. Slide one window of length minSize, keeping letter counts
    # so the distinct-letter total is available in constant time per step.
    n = len(s)
    if minSize > n:
        return 0
    freq = {}
    tally = {}
    for i, ch in enumerate(s):
        freq[ch] = freq.get(ch, 0) + 1
        if i >= minSize:
            gone = s[i - minSize]
            freq[gone] -= 1
            if freq[gone] == 0:
                del freq[gone]
        if i >= minSize - 1 and len(freq) <= maxLetters:
            piece = s[i - minSize + 1:i + 1]
            tally[piece] = tally.get(piece, 0) + 1
    best = 0
    for v in tally.values():
        if v > best:
            best = v
    return best

The obvious version

Try every allowed length from minSize to maxSize. For each length, cut out every stretch of that length, drop the ones using too many distinct letters, tally the rest in a dictionary, and remember the biggest tally seen across all lengths.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_max_freq(s, maxLetters, minSize, maxSize):
    n = len(s)
    best = 0
    for size in range(minSize, maxSize + 1):
        counts = {}
        for start in range(0, n - size + 1):
            piece = s[start:start + size]
            if len(set(piece)) <= maxLetters:
                counts[piece] = counts.get(piece, 0) + 1
        for v in counts.values():
            if v > best:
                best = v
    return best

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in