Incorrect problem description. #32082
Description
LeetCode Username
Iam_Prashanth
Problem Number, Title, and Link
https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/
Bug Category
Problem description
Bug Description
The current statement correctly requires substrings to have length between minSize and maxSize and at most maxLetters distinct characters. However, many solvers are confused and attempt to check all lengths between minSize and maxSize. It would be helpful if the problem page (or editorial) included a short note that for the purpose of maximizing occurrence count you only need to consider substrings of length minSize.
Brief justification to include: For any valid substring T with length L ≥ minSize, take its prefix P of length minSize. Every occurrence of T implies an occurrence of P at the same position, and P cannot have more distinct characters than T. Therefore count(P) ≥ count(T), so the maximum frequency is achieved by some substring of length exactly minSize.
Example:
Consider s = "aabcjfkfaabc", minSize = 3, maxSize = 5.
"aa" occurs 2 times
"aab" occurs 2 times
"aabc" occurs 2 times
Although "aa" (length 2) and "aabc" (length 4) also occur the same number of times, the maximum is already captured by "aab" (length minSize = 3). Any longer valid substring cannot have a higher frequency than its minSize prefix.
Language Used for Code
Python/Python3
Code used for Submit/Run operation
class Solution:
def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
n=len(s)
mp=defaultdict(int)
for i in range(n-minSize+1):
s1=s[i:i+minSize]
if len(set(s1))<=maxLetters:
mp[s1]+=1
return max(mp.values()) if mp else 0Expected behavior
Adding this note will prevent unnecessary brute-force attempts over many lengths and will guide users to the intended efficient solution. Thanks!
Screenshots
No response
Additional context
No response