-
-
Notifications
You must be signed in to change notification settings - Fork 9.5k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
【每日一题】- 2020-01-08 - 1297. 子串的最大出现次数 #266
Comments
Java题解 简单明了 注意题目细节中的maxSize范围,那么就可以发现暴力解法可以做。 其实可以用滑动窗口来做,窗口大小为minSize即可。理由大致如下:
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
Map<String, Integer> counter = new HashMap<>();
int res = 0;
for (int i = 0; i < s.length() - minSize + 1; i++) {
String substr = s.substring(i, i + minSize);
if (checkNum(substr, maxLetters)) {
int newVal = counter.getOrDefault(substr, 0) + 1;
counter.put(substr, newVal);
res = Math.max(res, newVal);
}
}
return res;
}
public boolean checkNum(String substr, int maxLetters) {
Set<Character> set = new HashSet<>();
for (int i = 0; i < substr.length(); i++)
set.add(substr.charAt(i));
return set.size() <= maxLetters;
} |
@unclegem 一看就知道高手, 看条件看的这么犀利 做了不少题吧? |
😂还好,就是有的题范围卡的松,一般第一种解法就上bf试试了。 |
@unclegem Similar Solution with Python3, But TLE: # https://leetcode-cn.com/problems/maximum-number-of-occurrences-of-a-substring/
class Solution:
def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
n = len(s)
letters = set()
cnts = dict()
res = 0
for i in range(n - minSize + 1):
length = minSize
while i + length <= n and length <= maxSize:
t = s[i:i + length]
for c in t:
if len(letters) > maxLetters:
break
letters.add(c)
if len(letters) <= maxLetters:
cnts[t] = cnts.get(t, 0) + 1
res = max(res, cnts[t])
letters.clear()
length += 1
return res |
你这个窗口大小没固定的吧,固定为minSize应该不会超时。 |
@unclegem wow |
这样不会TLE了 def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
counter, res = {}, 0
for i in range(0, len(s) - minSize + 1):
sub = s[i : i + minSize]
if len(set(sub)) <= maxLetters:
counter[sub] = counter.get(sub, 0) + 1
res = max(res, counter[sub])
return res; |
@unclegem big thanks for u ❤️ # https://leetcode-cn.com/problems/maximum-number-of-occurrences-of-a-substring/
class Solution:
def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
n = len(s)
letters = set()
cnts = dict()
res = 0
for i in range(n - minSize + 1):
t = s[i:i + minSize]
for c in t:
if len(letters) > maxLetters:
break
letters.add(c)
if len(letters) <= maxLetters:
cnts[t] = cnts.get(t, 0) + 1
res = max(res, cnts[t])
letters.clear()
return res |
TQL |
This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions. |
补充: 这道题的 maxSize 是无用信息, 并不需要用到。 |
给你一个字符串 s ,请你返回满足以下条件且出现次数最大的 任意 子串的出现次数:
子串中不同字母的数目必须小于等于 maxLetters 。
子串的长度必须大于等于 minSize 且小于等于 maxSize 。
示例 1:
输入:s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
输出:2
解释:子串 "aab" 在原字符串中出现了 2 次。
它满足所有的要求:2 个不同的字母,长度为 3 (在 minSize 和 maxSize 范围内)。
示例 2:
输入:s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
输出:2
解释:子串 "aaa" 在原字符串中出现了 2 次,且它们有重叠部分。
示例 3:
输入:s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3
输出:3
示例 4:
输入:s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
输出:0
提示:
1 <= s.length <= 10^5
1 <= maxLetters <= 26
1 <= minSize <= maxSize <= min(26, s.length)
s 只包含小写英文字母。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-number-of-occurrences-of-a-substring
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
The text was updated successfully, but these errors were encountered: