LeetCode 2981: 找出出现至少三次的最长特殊子串 I 1. 题目详解 1.1 原始题目 给你一个仅由小写英文字母组成的字符串 s 。
如果一个字符串仅由单一字符组成，则称它是一个 特殊字符串 。例如，字符串 “abc” 不是特殊字符串，而字符串 “ddd”、”zz” 和 “f” 是特殊字符串。
返回在 s 中出现 至少三次 的最长特殊子串的长度，如果不存在出现至少三次的特殊子串，则返回 -1 。
子串 是一个字符串中一段连续的字符序列。
1.2 题目约束
3 <= s.length <= 50
s 仅由小写英文字母组成
1.3 题意分析
特殊字符串的定义 ：
只包含单一字符的字符串
长度可以是任意的（1到字符串长度）
例如：”aaa”是特殊字符串，”abc”不是
子串要求 ：
必须是连续的字符序列
需要在原字符串中出现至少三次
寻找满足条件的最长长度
返回值 ：
如果存在符合条件的特殊子串，返回最长的长度
如果不存在，返回-1
1.4 示例详解 示例1： 1 2 3 4 5 6 7 8 输入：s = "aaaa" 输出：2 解释： - 长度为1的特殊子串"a"出现4次 - 长度为2的特殊子串"aa"出现3次 - 长度为3的特殊子串"aaa"出现2次 - 长度为4的特殊子串"aaaa"出现1次 所以最长的出现至少三次的特殊子串长度为2
示例2： 1 2 3 4 5 输入：s = "abcdef" 输出：-1 解释： - 所有特殊子串（单个字符）都只出现一次 - 不存在出现至少三次的特殊子串
示例3： 1 2 3 4 5 6 输入：s = "abcaba" 输出：1 解释： - 字符'a'在位置0、3、5出现三次 - 没有更长的特殊子串出现三次 - 所以返回长度1
2. 解法1：基础哈希表法 2.1 思路
使用哈希表存储每个特殊子串及其出现次数
遍历字符串，对于每个位置：
如果当前字符与前一个字符不同，开始新的特殊子串
如果相同，扩展当前特殊子串并统计所有可能长度
最后筛选出现至少三次的最长子串
2.2 详细代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution: def maximumLength(self, s: str) -> int: # 存储特殊子串及其出现次数 dict_special_substrings = {s[0]: 1} sub_start = 0 # 当前特殊子串的起始位置 sub_end = 1 # 当前特殊子串的结束位置 # 辅助函数：更新子串计数 def add_to_dict(substrings): if substrings not in dict_special_substrings: dict_special_substrings[substrings] = 1 else: dict_special_substrings[substrings] += 1 # 遍历字符串 for idx in range(1, len(s)): if s[idx] != s[idx - 1]: # 遇到不同字符 sub_start = idx sub_end = idx + 1 add_to_dict(s[sub_start:sub_end]) else: # 遇到相同字符 sub_end += 1 # 统计所有可能长度的子串 for j in range(sub_start + 1, sub_end + 1): add_to_dict(s[sub_start:j]) # 筛选出现至少3次的子串 dict_special_substrings_filter = { k: v for k, v in dict_special_substrings.items() if v >= 3 } # 返回最长长度或-1 if len(dict_special_substrings_filter) == 0: return -1 else: # 按长度降序排序 sorted_items = sorted( dict_special_substrings_filter.items(), key=lambda item: len(item[0]), reverse=True, ) k, v = sorted_items[0] return len(k)
2.3 示例执行过程 以输入 "aaaa" 为例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 初始状态：dict_special_substrings = {"a": 1} 第1次循环 (idx=1)： - s[1] == s[0]，扩展当前子串 - 添加 "a" 和 "aa" - dict_special_substrings = {"a": 2, "aa": 1} 第2次循环 (idx=2)： - s[2] == s[1]，扩展当前子串 - 添加 "a"、"aa" 和 "aaa" - dict_special_substrings = {"a": 3, "aa": 2, "aaa": 1} 第3次循环 (idx=3)： - s[3] == s[2]，扩展当前子串 - 添加 "a"、"aa"、"aaa" 和 "aaaa" - dict_special_substrings = {"a": 4, "aa": 3, "aaa": 2, "aaaa": 1} 筛选后：{"a": 4, "aa": 3} 返回：2（"aa"的长度）
2.4 复杂度分析
时间复杂度 ：O(n²)
外层循环遍历字符串：O(n)
内层循环统计子串：O(n)
排序操作：O(k log k)，其中k是特殊子串数量
空间复杂度 ：O(n²)
3. 解法2：优化的计数法 3.1 思路
使用(字符, 长度)作为键来统计频率，避免存储实际子串
通过数学公式计算子串数量，避免实际生成子串
一次遍历完成所有计算，大幅提升效率
3.2 详细代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution: def maximumLength(self, s: str) -> int: # 使用字典存储(字符,长度)对应的出现次数 counts = {} curr_len = 1 # 当前连续相同字符的长度 # 遍历字符串（包含最后一个字符的处理） for i in range(1, len(s) + 1): # 当前字符与前一个字符相同，增加连续长度 if i < len(s) and s[i] == s[i-1]: curr_len += 1 else: char = s[i-1] # 计算所有可能长度的子串数量 for length in range(1, curr_len + 1): # 核心公式：curr_len - length + 1 计算特定长度的子串出现次数 counts[(char, length)] = counts.get((char, length), 0) + curr_len - length + 1 curr_len = 1 # 找出最大的满足条件的长度 result = -1 for (char, length), freq in counts.items(): if freq >= 3: result = max(result, length) return result
3.3 核心公式解释 对于连续序列长度为n的情况，长度为k的子串出现次数计算公式：n - k + 1
例如，对于序列 “aaaa” (n=4)：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 长度为1的子串 "a"： - 位置0开始：a - 位置1开始：a - 位置2开始：a - 位置3开始：a 总数 = 4 - 1 + 1 = 4次 长度为2的子串 "aa"： - 位置0开始：aa - 位置1开始：aa - 位置2开始：aa 总数 = 4 - 2 + 1 = 3次 长度为3的子串 "aaa"： - 位置0开始：aaa - 位置1开始：aaa 总数 = 4 - 3 + 1 = 2次 长度为4的子串 "aaaa"： - 位置0开始：aaaa 总数 = 4 - 4 + 1 = 1次
3.4 示例执行过程 以输入 "aaabbb" 为例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 第一段 "aaa": curr_len = 3 处理 'a': - counts[('a', 1)] = 3 # 长度1出现3次 - counts[('a', 2)] = 2 # 长度2出现2次 - counts[('a', 3)] = 1 # 长度3出现1次 第二段 "bbb": curr_len = 3 处理 'b': - counts[('b', 1)] = 3 # 长度1出现3次 - counts[('b', 2)] = 2 # 长度2出现2次 - counts[('b', 3)] = 1 # 长度3出现1次 最终结果：1（最长的出现至少3次的特殊子串长度为1）
3.5 复杂度分析
时间复杂度 ：O(n)
只需要遍历一次字符串
内层循环的总执行次数不会超过字符串长度
空间复杂度 ：O(n)
4. 解法3：前缀和法 4.1 思路
使用嵌套的defaultdict记录每个字符的不同长度出现次数
通过前缀和快速判断是否存在足够的子串
从大到小遍历长度，找到符合条件的最大长度
4.2 详细代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 from collections import defaultdict class Solution: def maximumLength(self, s: str) -> int: # 创建嵌套的defaultdict，避免键不存在的检查 freq = defaultdict(lambda: defaultdict(int)) pre = s[0] # 前一个字符 length = 1 # 当前连续长度 # 初始化第一个字符 freq[s[0]][1] = 1 # 遍历字符串 for i in range(1, len(s)): cur = s[i] if cur == pre: # 当前字符与前一个相同 length += 1 freq[cur][length] += 1 else: # 遇到新字符 freq[cur][1] += 1 pre = cur length = 1 # 查找最长满足条件的长度 ans = -1 for k in freq.keys(): # 遍历每个字符 presum = 0 # 从大到小遍历可能的长度 for j in range(len(s), 0, -1): presum += freq[k][j] # 累加前缀和 if presum >= 3: # 找到满足条件的长度 ans = max(ans, j) break return ans
4.3 示例执行过程 以输入 "aabaa" 为例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 初始化：freq['a'][1] = 1 处理 'a'： freq['a'][2] = 1 处理 'b'： freq['b'][1] = 1 处理 'a'： freq['a'][1] += 1 处理 'a'： freq['a'][2] += 1 最终freq状态： 'a': {1: 2, 2: 2} 'b': {1: 1} 前缀和检查： 对于'a'： - 长度2：presum = 2 < 3 - 长度1：presum = 4 >= 3 ✓ 对于'b'： - 长度1：presum = 1 < 3 返回：1
4.4 复杂度分析
时间复杂度 ：O(n)
遍历字符串：O(n)
对每个字符的前缀和计算：O(1)
空间复杂度 ：O(n)
5. 总结与比较 5.1 三种解法比较
基础哈希表法
优化的计数法
前缀和法
5.2 选择建议
面试时建议使用解法2或解法3
解法2更容易解释和理解
实际应用中三种解法都是可接受的
5.3 扩展思考
如何处理更大规模的输入？
如何并行化处理？
如何处理流式输入？
