718. The Commonest Substring Under Two Limits
Among the substrings that use at most maxLetters DISTINCT letters and whose length is
between minSize and maxSize inclusive, print the largest number of times any one of them
occurs. Print 0 if none qualifies.
aababcaab, maxLetters = 2, minSize = 3, maxSize = 4 -> 2 aab occurs twice
aabcabcab, maxLetters = 2, minSize = 2, maxSize = 3 -> 3 ab occurs three times
abcde, maxLetters = 2, minSize = 3, maxSize = 3 -> 0
## maxSize does not matter
This is the point of the problem, and it is worth reasoning to rather than being told.
Take any qualifying substring of length L > minSize occurring t times. Its first
minSize characters form a shorter substring that occurs AT LEAST t times, once inside each
of those occurrences. And it uses no more distinct letters, since it is a prefix.
So the shorter one is at least as good on both counts, and no length above minSize can ever
be a strict winner. Checking length minSize alone is enough, and maxSize can be read and
discarded.
A statement that hands you an irrelevant parameter is testing whether you will check.
## One fixed window of width minSize
Slide a window of exactly minSize characters, carrying a per letter tally and the count of
distinct letters currently inside. When that count is at most maxLetters, tally the
substring itself in a map and track the best.
add s[i] # distinct += 1 when its tally becomes 1
if i >= L: remove s[i - L] # distinct -= 1 when its tally hits 0
if i >= L - 1 and distinct <= maxLetters:
seen[substring] += 1
best = max(best, seen[substring])
## The thresholds again
distinct moves when a tally crosses ZERO, so the tests are tally == 0 before incrementing
and tally == 0 after decrementing. This is the same crossing rule as problem 704, where the
threshold was 2 and 1 instead of 0 and 1 because the quantity being tracked was different.
## Boundaries
minSize larger than the string gives 0. maxLetters at least 26 removes the distinctness
constraint entirely, leaving the commonest substring of length minSize.
## Cost
Time O(n * minSize), dominated by hashing each window's substring. Space O(n * minSize)
for the map in the worst case.
Constraints - `1 ≤ length ≤ 100000` - `1 ≤ maxLetters ≤ 26` - `1 ≤ minSize ≤ maxSize ≤ 26` - every character is a lowercase letter
Input
The first line contains the string.
The second line contains three integers: maxLetters, minSize and maxSize.
Output
Print one integer, the largest number of occurrences.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.