2981.找出出现至少三次的最长特殊子字符串I
题目:
给你一个仅由小写英文字母组成的字符串 s
。
如果一个字符串仅由单一字符组成,那么它被称为 特殊 字符串。例如,字符串 "abc"
不是特殊字符串,而字符串 "ddd"
、"zz"
和 "f"
是特殊字符串。
返回在 s
中出现 至少三次 的 最长特殊子字符串 的长度,如果不存在出现至少三次的特殊子字符串,则返回 -1
。
子字符串 是字符串中的一个连续 非空 字符序列。
示例 1:
输入:s = "aaaa" 输出:2 解释:出现三次的最长特殊子字符串是 "aa" :子字符串 "aaaa"、"aaaa" 和 "aaaa"。 可以证明最大长度是 2 。
示例 2:
输入:s = "abcdef" 输出:-1 解释:不存在出现至少三次的特殊子字符串。因此返回 -1 。
示例 3:
输入:s = "abcaba" 输出:1 解释:出现三次的最长特殊子字符串是 "a" :子字符串 "abcaba"、"abcaba" 和 "abcaba"。 可以证明最大长度是 1 。
提示:
3 <= s.length <= 50
s
仅由小写英文字母组成。
分析:
刚开始看了这道题十几分钟没思路,写了又删,删了又写。后来也是看了评论区的题解,整理了以下思路:
"""
1.设字母a的最长特殊子串的长度是L1
那么可以选3个长为 L1-2 的相同的特殊子串2.设字母a的第二长特殊子串的长度是L2
如果 L1=L2.选 3 个长为L1-1的
如果 L1>L2.选 3 个长为L2的
min(L1-1,L2)3.设字母a的第三长特殊子串的长度为L3
那么可以选3个长为L3的相同的特殊子串max(L1-2,min(L1-1,L2),L3)"""
代码实现:
class Solution:def maximumLength(self, s: str) -> int:groups = defaultdict(list) # hashmap key:char value:listcnt=0for i ,ch in enumerate(s):# ch =s[i]cnt+=1if i==len(s)-1 or ch!=s[i+1]:groups[ch].append(cnt)cnt=0print(groups)ans=0for a in groups.values():a.sort(reverse=True)a.extend([0,0]) # 防止只有一个数 报错l1,l2,l3 = a[:3] # 新写法ans = max(ans,l1-2,min(l1-1,l2),l3)return ans if ans else -1 # ans大于0 返回ans 否则返回-1
a=Solution()
b=a.maximumLength(s='aaaaba')
print(b)
总结:
这道题引入了新知识点,defaultdict()模块。
defaultdict()详解:
defaultdict是collections模块中的一个类,它是一种字典的子类,它允许使用默认值来创建一个字典。当我们访问一个不存在的键时,defaultdict会自动创建这个键,并将其对应的值初始化为一个默认值。
默认值可以是任何类型,例如int、list、set、dict等。这样当我们需要向一个默认值为空的字典中添加元素时,就不需要担心键是否存在的问题,因为defaultdict会自动帮我们处理这个情况。
使用defaultdict可以更加简洁和高效地处理一些问题,特别是在需要处理大量数据或者复杂数据结构时。下面是一个使用defaultdict的例子:
from collections import defaultdict# 创建一个defaultdict,指定默认值为list
d = defaultdict(list)# 使用defaultdict来向字典中添加元素
d['a'].append(1)
d['b'].append(2)
d['c'].append(3)print(d) # 输出 defaultdict(<class 'list'>, {'a': [1], 'b': [2], 'c': [3]})
在上面的例子中,当我们尝试向字典d中的不存在的键添加元素时,defaultdict会自动为这个键初始化一个空列表,并将元素添加到这个列表中。这样就避免了使用普通字典时需要先判断键是否存在的繁琐操作。
不仅如此,还巧妙的用了extend([]) ,这样有效的防止了只有一个长度的报错情况。很敬佩这种思路。
不断的突破,创新,提高!这正是我所追求的!