小程序组件化,提高效率的解决方案
545
2022-09-05
[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
参考文献
[LeetCode] Python Sliding Window
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~