力扣每日一题 5/30

2982.找出出现至少三次的最长特殊子字符串II  [中等]

给你一个仅由小写英文字母组成的字符串 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 <= 5 * 105
• s 仅由小写英文字母组成。

分析：

       这道题和昨天的题目一样，不过对复杂度的要求提高了，因为可以看到s的长度有明显增加。这就要求代码的复杂度尽可能小了。不过昨天的代码时间复杂度并不高，这道题依然可以AC。

       不过我根据昨天的思路，今天重新敲了一遍代码，和昨天的代码略微不同 但思路大同小异。

代码实现：

class Solution:
    def maximumLength(self, s: str) -> int:
        dic={}
        n=len(s)
        cos=0
        for i in range(n):
            cos+=1
            if i==n-1 or s[i]!=s[i+1]:
                if s[i] not in dic:
                    dic[s[i]]=[cos]
                else: dic[s[i]].append(cos)
                cos=0
        print(dic)
        a_max=0
        for j in dic.values():
            j.sort(reverse=True)
            j.extend([0,0])
            print(j)
            # if j[0]>=3:
            key=max(j[0]-2,min(j[0]-1,j[1]),j[2])
            if key>a_max: a_max=key
        if a_max==0: return -1
        return a_max 
a=Solution()
b=a.maximumLength(s='aaabaa')
print(b)

总结：

       昨天同样的题没有一点思路，看完解析后今天又一样的题，就应该独自代码实现，不仅可以巩固知识还可以自我检测。这串代码在时间和空间上都可以击败超越70%的Python用户，性能还是无可置疑的。