LeetCode 题解工作台
找出出现至少三次的最长特殊子字符串 I
给你一个仅由小写英文字母组成的字符串 s 。 如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd" 、 "zz" 和 "f" 是特殊字符串。 返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊…
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
我们注意到，如果一个长度为 且出现至少三次的特殊子字符串存在，那么长度为 的特殊子字符串也一定存在，这存在着单调性，因此我们可以使用二分查找的方法来找到最长的特殊子字符串。 我们定义二分查找的左边界 $l = 0$，右边界 $r = n$，其中 是字符串的长度。每次二分查找的过程中，我们取 $mid = \lfloor \frac{l + r + 1}{2} \rfloor$，如果长度为 …
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个仅由小写英文字母组成的字符串 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 <= 50s仅由小写英文字母组成。
解题思路
方法一：二分查找 + 滑动窗口计数
我们注意到，如果一个长度为 且出现至少三次的特殊子字符串存在，那么长度为 的特殊子字符串也一定存在，这存在着单调性，因此我们可以使用二分查找的方法来找到最长的特殊子字符串。
我们定义二分查找的左边界 ，右边界 ，其中 是字符串的长度。每次二分查找的过程中，我们取 ，如果长度为 的特殊子字符串存在，那么我们就将左边界更新为 ，否则我们就将右边界更新为 。在二分查找的过程中，我们使用滑动窗口来计算特殊子字符串的个数。
具体地，我们设计一个函数 ，表示长度为 且出现至少三次的特殊子字符串是否存在。
在函数 中，我们定义一个哈希表或长度为 的数组 ，其中 表示长度为 ，且由第 个小写字母组成的特殊子字符串的个数。我们遍历字符串 ，如果当前遍历到的字符为 ，那么我们将指针 向右移动，直到 ，此时 就是一个长度为 的特殊子字符串，我们将 增加 ，然后将指针 更新为 。
在遍历结束之后，我们遍历数组 ，如果存在 ，那么就说明长度为 且出现至少三次的特殊子字符串存在，我们返回 ，否则返回 。
时间复杂度 ，空间复杂度 ，其中 是字符串 的长度，而 表示字符集的大小，本题中字符集为小写英文字母，因此 。
class Solution:
def maximumLength(self, s: str) -> int:
def check(x: int) -> bool:
cnt = defaultdict(int)
i = 0
while i < n:
j = i + 1
while j < n and s[j] == s[i]:
j += 1
cnt[s[i]] += max(0, j - i - x + 1)
i = j
return max(cnt.values()) >= 3
n = len(s)
l, r = 0, n
while l < r:
mid = (l + r + 1) >> 1
if check(mid):
l = mid
else:
r = mid - 1
return -1 if l == 0 else l
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n^2) |
| 空间 | O(n^2) |
面试官常问的追问
外企场景- question_mark
Candidate uses binary search to optimize substring length checking.
- question_mark
Candidate correctly applies a hash table to count substring occurrences efficiently.
- question_mark
Candidate demonstrates a clear understanding of sliding window techniques for substring extraction.
常见陷阱
外企场景- error
Not properly handling edge cases where no valid special substring exists, leading to incorrect output.
- error
Failure to optimize the search space with binary search, resulting in inefficient solutions.
- error
Not correctly updating the count of substrings in the hash table, causing wrong results.
进阶变体
外企场景- arrow_right_alt
Consider strings with multiple possible special substrings of different lengths.
- arrow_right_alt
Optimize for larger inputs by adjusting the binary search space or improving hash table usage.
- arrow_right_alt
Explore solutions using different data structures to manage substring counts, such as arrays.