[leetcode] 1297. Maximum Number of Occurrences of a Substring

网友投稿 545 2022-09-05

[leetcode] 1297. Maximum Number of Occurrences of a Substring

[leetcode] 1297. Maximum Number of Occurrences of a Substring

Description

Given a string s, return the maximum number of ocurrences of any substring under the following rules:

The number of unique characters in the substring must be less than or equal to maxLetters.The substring size must be between minSize and maxSize inclusive.

Example 1:

Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4Output: 2Explanation: Substring "aab" has 2 ocurrences in the original string.It satisfies the conditions, 2 unique letters and size 3 (between minSize and maxSize).

Example 2:

Input: s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3Output: 2Explanation: Substring "aaa" occur 2 times in the string. It can overlap.

Example 3:

Input: s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3Output: 3

Example 4:

Input: s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3Output: 0

Constraints:

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

分析

题目的意思是:求一个字符串里面出现频率最大的子字符串。字符串的长度和包含字母的个数都有限制。题目我一开始没看太懂,后面发现是一个类似双指针滑动窗口的问题,这里i表示左边界,j表示右边界,当j-i满足限制条件时,用res来统计子序列的频率,最后求出res的最大值就是所求了。

代码

class Solution: def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int: j=0 cur=collections.defaultdict(int) res=collections.defaultdict(int) i=0 while(j=minSize and j-i<=maxSize): if(len(cur)<=maxLetters): res[s[i:j]]+=1 cur[s[i]]-=1 if(cur[s[i]]==0): del cur[s[i]] i+=1 if(res): return max(res.values()) return 0

参考文献

​​[LeetCode] Python Sliding Window​​

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:几款主流 NoSql 数据库的对比
下一篇:python3 os remove,rename代码重命名和删除文件简单示例
相关文章

 发表评论

暂时没有评论,来抢沙发吧~