找出出现至少三次的最长特殊子字符串 II

标签: 哈希表 字符串 二分查找 计数 滑动窗口

难度: Medium

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

Submission

运行时间: 211 ms

内存: 18.6 MB

class Solution:
    def maximumLength(self, s: str) -> int:
        c = defaultdict(lambda: defaultdict(int))
        cur = s[0]
        cnt = 1
        l = len(s)
        for a in s[1:]:
            if cur == a:
                cnt += 1
            else:
                c[cur][cnt] += 1
                cur = a
                cnt = 1
        c[cur][cnt] += 1
        ans = 0
        for nl in c.values():
            ma = max(nl)
            if nl[ma] >= 3:
                if ans < ma:
                    ans = ma
            elif nl[ma] == 2 or nl[ma - 1]:
                if ans < ma - 1:
                    ans = ma - 1
            elif ans < ma - 2:
                ans = ma - 2
        return ans if ans else -1

Explain

这个题解的思路是先统计字符串s中连续相同字符的段，并记录每个字符出现的次数及其长度。然后遍历这些记录，寻找出现至少三次的最长特殊子字符串的长度。如果一个字符的最长连续段出现次数大于等于3，那么这个长度就是候选答案。如果出现次数是2或者前一个长度的段存在，则答案可以是最长长度减1。否则，答案可以是最长长度减2。最后返回找到的最长长度，如果没有找到，则返回-1。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maximumLength(self, s: str) -> int:
        c = defaultdict(lambda: defaultdict(int))  # 初始化记录字典
        cur = s[0]  # 当前字符
        cnt = 1  # 当前字符连续出现次数
        l = len(s)  # 字符串长度
        for a in s[1:]:
            if cur == a:  # 如果当前字符和前一个字符相同
                cnt += 1
            else:
                c[cur][cnt] += 1  # 记录当前字符和长度
                cur = a  # 更新当前字符
                cnt = 1  # 重置计数器
        c[cur][cnt] += 1  # 处理最后一个字符
        ans = 0  # 初始化答案
        for nl in c.values():  # 遍历记录的字符
            ma = max(nl)  # 获取最长连续长度
            if nl[ma] >= 3:  # 如果出现次数大于等于3
                if ans < ma:
                    ans = ma
            elif nl[ma] == 2 or nl[ma - 1]:  # 如果出现次数等于2或前一个长度存在
                if ans < ma - 1:
                    ans = ma - 1
            elif ans < ma - 2:  # 其他情况
                ans = ma - 2
        return ans if ans else -1  # 如果找到答案则返回，否则返回-1

Explore

在Python中，使用defaultdict(int)可以自动初始化每个键的默认值为0，这样在更新键值时可以直接进行加法操作，而不需要先检查键是否存在于字典中。这样做可以减少代码的复杂度和执行条件判断的次数，从而提高代码的执行效率。使用普通字典在每次更新之前需要手动检查和初始化键，这会增加额外的执行步骤和可能的错误点。

在字符变更时更新字典是因为只有当当前字符与前一个字符不同时，前一个字符的连续段才真正结束，此时可以准确地记录该字符段的长度和出现次数。至于字符串末尾的字符序列，代码中在循环结束后有一行专门处理最后一个字符段的记录（`c[cur][cnt] += 1`），确保了字符串末尾的字符序列也被正确统计。

这种处理逻辑是基于找寻次长的可行子字符串长度的考虑。当一个字符段的最长长度出现次数不足以直接成为答案时（如只出现了2次），则考虑长度稍短一点（最长长度减1）的子字符串可能满足条件（因为它们可能出现次数更多）。另外，如果存在长度为最长长度减1的其他字符段，这也表明该长度的字符串有足够的出现频率，可能是一个有效的答案。

是的，如果某个字符的连续字符段的最大长度为1且出现次数至少为3次，那么答案应该是1。题解中的逻辑中，对于任何出现至少三次的最长连续段，都会考虑作为答案，包括长度为1的情况。因此，即使题解中没有特别提到这种情况，按照代码逻辑，这种情况下的答案也确实是1。