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

解题思路及代码

看到条件+子字符串/子序列就马上想到要使用快慢指针，先捋一下解题思路。

至少三次 的 最长特殊子字符串
子字符串 是字符串中的一个连续非空字符序列
字符串仅由单一字符组成

结合以上条件，我们可以直接套用标准模板来实现

ans,left,right = -1,0,0

while right < len(s):
	计算r相关
	while left不满足条件:
		移动l
	r++
return ans

# [a, a, a, a, a]
# l↑
#    r↑
# 此时 s[left] == s[right]，right 右移，继续循环

# [a, a, a, a, a]
# l↑
#        r↑
# 此时 s[left] == s[right]，right 右移，继续循环

# [a, a, a, a, a]
# l↑
#             r↑
# 此时 s[left] == s[right]，right 右移，继续循环

但是在这一题里面我们不需要完全套用只需要一个循环来控制right的移动，再通过dict来记录全部出现的符合要求的特殊子串并输出ans

双指针/快慢指针/滑动窗口:

from collections import defaultdict


class Solution:
    def maximumLength(self, s: str) -> int:
        hash_map = defaultdict(int)
        left, right = 0, 0
        while right < len(s):
            # 如果当前值与下一个值相同，那么他就是一个特殊字符串
            # 又因为left的相对不动的，right是移动的，只需要拿她们比对即可
            if s[left] == s[right]:
                # left-right区间内的值都相同，right 移动一位
                right += 1
                continue
            else:
                # left 不等于 right
                # 就代表当前最长串的特殊字符为 right - left
                # 且字符串为 s[left] * right - left
                # 特殊字符本身也是包含 特殊字符串的 aaaaa -> aa aa, a aa a, aa aa,
                continuous_length = right - left
                continuous_str = s[left]
                for i in range(continuous_length):
                    # += 是因为还可能存在一个这样的特殊字符，
                    # 通过特殊字符串aaaaa -> aa aa, a aa a, aa aa,
                    # 可以知道在特殊字符中的子特殊字符出现次数 = 长度- (字串长度-1)
                    # 内部for循环执行情况

                    # 加假如 right - left =5 , str = "a"
                    # i=0：hash_map['a'] = 5 (将5个'a'计算进去)
                    # i=1：hash_map['aa'] = 4 (将4个'aa'计算进去)
                    # i=2：hash_map['aaa'] = 3 ...
                    # i=3：hash_map['aaaa'] = 2 ...
                    # i=4：hash_map['aaaaa'] = 1 ...
                    hash_map[continuous_str * (i + 1)] += continuous_length - i
                left = right

        # s可能就是一个合格的特殊字子串不会到 else 中去
        continuous_length = right - left
        continuous_str = s[left]
        for i in range(continuous_length):
            hash_map[continuous_str * (i + 1)] += continuous_length - i

        ans = -1
        for key, val in hash_map.items():
            if val >= 3:
                ans = max(ans, len(key))
        return ans

复杂度分析

时间复杂度：
- 主循环为O(n)
- 内嵌的for O(n)
- 输出结果 O(n)

在最坏的情况下，时间复杂度为O(n^3) ，一般情况下我们理解为O(n^2)

空间复杂度：O(n) 用来存储子字符串和对应的频率。